Codeforces 258E — Little Elephant and Tree

1package main2 3import (4	. "fmt"5	"io"6	"math/bits"7)8 9// https://github.com/EndlessCheng10type seg58 []struct{ l, r, s, minCover, todo int }11 12func (t seg58) maintain(o int) {13	lo, ro := &t[o<<1], &t[o<<1|1]14	mn := min(lo.minCover, ro.minCover)15	t[o].minCover = mn16	t[o].s = 017	if lo.minCover == mn {18		t[o].s = lo.s19	}20	if ro.minCover == mn {21		t[o].s += ro.s22	}23}24 25func (t seg58) do(o, v int) {26	t[o].minCover += v27	t[o].todo += v28}29 30func (t seg58) spread(o int) {31	v := t[o].todo32	if v != 0 {33		t.do(o<<1, v)34		t.do(o<<1|1, v)35		t[o].todo = 036	}37}38 39func (t seg58) build(o, l, r int) {40	t[o].l, t[o].r = l, r41	if l == r {42		t[o].s = 143		return44	}45	m := (l + r) >> 146	t.build(o<<1, l, m)47	t.build(o<<1|1, m+1, r)48	t.maintain(o)49}50 51func (t seg58) update(o, l, r, v int) {52	if l <= t[o].l && t[o].r <= r {53		t.do(o, v)54		return55	}56	t.spread(o)57	m := (t[o].l + t[o].r) >> 158	if l <= m {59		t.update(o<<1, l, r, v)60	}61	if m < r {62		t.update(o<<1|1, l, r, v)63	}64	t.maintain(o)65}66 67func cf258E(in io.Reader, out io.Writer) {68	var n, m, dfn int69	Fscan(in, &n, &m)70	g := make([][]int, n)71	for range n - 1 {72		var v, w int73		Fscan(in, &v, &w)74		v--75		w--76		g[v] = append(g[v], w)77		g[w] = append(g[w], v)78	}79 80	a := make([]struct{ l, r int }, n)81	dfnToV := make([]int, n)82	var dfs func(int, int)83	dfs = func(v, fa int) {84		a[v].l = dfn85		dfnToV[dfn] = v86		dfn++87		for _, w := range g[v] {88			if w != fa {89				dfs(w, v)90			}91		}92		a[v].r = dfn - 193	}94	dfs(0, -1)95 96	type event struct{ lx, rx, delta int }97	events := make([][]event, n+1)98	add := func(lx, ly, rx, ry int) {99		events[ly] = append(events[ly], event{lx, rx, 1})100		events[ry+1] = append(events[ry+1], event{lx, rx, -1})101	}102	for range m {103		var v, w int104		Fscan(in, &v, &w)105		p := a[v-1]106		q := a[w-1]107		add(p.l, p.l, p.r, p.r)108		add(p.l, q.l, p.r, q.r)109		add(q.l, p.l, q.r, p.r)110		add(q.l, q.l, q.r, q.r)111	}112 113	ans := make([]any, n)114	t := make(seg58, 2<<bits.Len(uint(n-1)))115	t.build(1, 0, n-1)116	for i, es := range events[:n] {117		for _, e := range es {118			t.update(1, e.lx, e.rx, e.delta)119		}120		res := n121		if t[1].minCover == 0 {122			res -= t[1].s123		}124		ans[dfnToV[i]] = max(res-1, 0)125	}126	Fprintln(out, ans...)127}128 129//func main() { cf258E(bufio.NewReader(os.Stdin), os.Stdout) }130