Codeforces 2033G — Sakurako and Chefir

1package main2 3import (4	. "fmt"5	"io"6	"math/bits"7)8 9// https://github.com/EndlessCheng10type seg33 []struct{ l, r, mx int }11 12func (t seg33) maintain(o int) {13	t[o].mx = max(t[o<<1].mx, t[o<<1|1].mx)14}15 16func (t seg33) build(o, l, r int) {17	t[o].l, t[o].r = l, r18	if l == r {19		return20	}21	m := (l + r) >> 122	t.build(o<<1, l, m)23	t.build(o<<1|1, m+1, r)24	t.maintain(o)25}26 27func (t seg33) update(o, i, val int) {28	if t[o].l == t[o].r {29		t[o].mx = val30		return31	}32	m := (t[o].l + t[o].r) >> 133	if i <= m {34		t.update(o<<1, i, val)35	} else {36		t.update(o<<1|1, i, val)37	}38	t.maintain(o)39}40 41func (t seg33) query(o, l, r int) int {42	if l <= t[o].l && t[o].r <= r {43		return t[o].mx44	}45	m := (t[o].l + t[o].r) >> 146	if r <= m {47		return t.query(o<<1, l, r)48	}49	if m < l {50		return t.query(o<<1|1, l, r)51	}52	return max(t.query(o<<1, l, r), t.query(o<<1|1, l, r))53}54 55func cf2033G(in io.Reader, out io.Writer) {56	var T, n, q int57	for Fscan(in, &T); T > 0; T-- {58		Fscan(in, &n)59		g := make([][]int, n)60		for range n - 1 {61			var v, w int62			Fscan(in, &v, &w)63			v--64			w--65			g[v] = append(g[v], w)66			g[w] = append(g[w], v)67		}68		Fscan(in, &q)69		type pair struct{ k, i int }70		qs := make([][]pair, n)71		for i := range q {72			var v, k int73			Fscan(in, &v, &k)74			qs[v-1] = append(qs[v-1], pair{k, i})75		}76 77		type tuple struct{ fi, se, w int }78		downDis := make([]tuple, n)79		var build func(int, int)80		build = func(v, fa int) {81			fi, se, fw := 0, 0, -282			for _, w := range g[v] {83				if w == fa {84					continue85				}86				build(w, v)87				d := downDis[w].fi + 188				if d > fi {89					se = fi90					fi, fw = d, w91				} else if d > se {92					se = d93				}94			}95			downDis[v] = tuple{fi, se, fw}96		}97		build(0, -1)98 99		maxD := downDis[0].fi100		t := make(seg33, 2<<bits.Len(uint(maxD)))101		t.build(1, 0, maxD)102 103		ans := make([]any, q)104		var dfs func(int, int, int)105		dfs = func(v, fa, d int) {106			for _, p := range qs[v] {107				if d == 0 || p.k == 0 {108					ans[p.i] = downDis[v].fi109				} else {110					ans[p.i] = max(t.query(1, max(d-p.k, 0), d-1)+d, downDis[v].fi)111				}112			}113			for _, w := range g[v] {114				if w == fa {115					continue116				}117				mx := downDis[v].fi118				if w == downDis[v].w {119					mx = downDis[v].se120				}121				t.update(1, d, mx-d)122				dfs(w, v, d+1)123			}124		}125		dfs(0, -1, 0)126		Fprintln(out, ans...)127	}128}129 130//func main() { cf2033G(bufio.NewReader(os.Stdin), os.Stdout) }131