Codeforces 1866K — Keen Tree Calculation

1package main2 3import (4	"bufio"5	"cmp"6	. "fmt"7	"io"8	"math/big"9	"slices"10	"sort"11)12 13// https://github.com/EndlessCheng14type vec66 struct{ x, y int }15 16func (a vec66) sub(b vec66) vec66 { return vec66{a.x - b.x, a.y - b.y} }17func (a vec66) dot(b vec66) int   { return a.x*b.x + a.y*b.y }18func (a vec66) detCmp(b vec66) int {19	v := new(big.Int).Mul(big.NewInt(int64(a.x)), big.NewInt(int64(b.y)))20	w := new(big.Int).Mul(big.NewInt(int64(a.y)), big.NewInt(int64(b.x)))21	return v.Cmp(w)22}23 24func cf1866K(in io.Reader, _w io.Writer) {25	out := bufio.NewWriter(_w)26	defer out.Flush()27	var n, Q, ans int28	Fscan(in, &n)29	type nb struct{ to, wt int }30	g := make([][]nb, n)31	for range n - 1 {32		var v, w, wt int33		Fscan(in, &v, &w, &wt)34		v--35		w--36		g[v] = append(g[v], nb{w, wt})37		g[w] = append(g[w], nb{v, wt})38	}39 40	nodes := make([]struct{ fi, se, fiW int }, n)41	var dfs func(int, int) int42	dfs = func(v, fa int) int {43		p := &nodes[v]44		for _, e := range g[v] {45			w := e.to46			if w == fa {47				continue48			}49			d := dfs(w, v) + e.wt50			ans = max(ans, p.fi+d)51			if d > p.fi {52				p.se = p.fi53				p.fi = d54				p.fiW = w55			} else if d > p.se {56				p.se = d57			}58		}59		return p.fi60	}61	dfs(0, -1)62 63	hulls := make([][2][]vec66, n)64	var reroot func(int, int, vec66)65	reroot = func(v, fa int, up vec66) {66		a := make([]vec66, len(g[v]))67		for i, e := range g[v] {68			w := e.to69			if w == fa {70				a[i] = up71			} else {72				a[i] = vec66{e.wt, nodes[w].fi}73			}74		}75 76		f := func(a, b vec66) int { return cmp.Or(a.x-b.x, a.y-b.y) }77		slices.SortFunc(a, f)78		q := a[:0]79		b := []vec66{}80		for _, v := range a {81			for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).detCmp(v.sub(q[len(q)-1])) >= 0 {82				b = append(b, q[len(q)-1])83				q = q[:len(q)-1]84			}85			q = append(q, v)86		}87		hulls[v][0] = q88 89		slices.SortFunc(b, f)90		q = b[:0]91		for _, v := range b {92			for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).detCmp(v.sub(q[len(q)-1])) >= 0 {93				q = q[:len(q)-1]94			}95			q = append(q, v)96		}97		hulls[v][1] = q98 99		p := nodes[v]100		for _, e := range g[v] {101			w := e.to102			if w == fa {103				continue104			}105			down := p.fi106			if w == p.fiW {107				down = p.se108			}109			reroot(w, v, vec66{e.wt, max(up.x+up.y, down)})110		}111	}112	reroot(0, -1, vec66{})113 114	Fscan(in, &Q)115	p := vec66{0, 1}116	for range Q {117		var v int118		Fscan(in, &v, &p.x)119		h := hulls[v-1][0]120		j := sort.Search(len(h)-1, func(j int) bool { return p.dot(h[j]) > p.dot(h[j+1]) })121		mx := p.dot(h[j])122		mx2 := 0123		if j > 0 {124			mx2 = p.dot(h[j-1])125		}126		if j < len(h)-1 {127			mx2 = max(mx2, p.dot(h[j+1]))128		}129		h = hulls[v-1][1]130		if len(h) > 0 {131			j := sort.Search(len(h)-1, func(j int) bool { return p.dot(h[j]) > p.dot(h[j+1]) })132			mx2 = max(mx2, p.dot(h[j]))133		}134		Fprintln(out, max(mx+mx2, ans))135	}136}137 138//func main() { cf1866K(bufio.NewReader(os.Stdin), os.Stdout) }139