Codeforces 932F — Escape Through Leaf

1package main2 3import (4	. "fmt"5	"io"6	"math/big"7	"sort"8)9 10// https://github.com/EndlessCheng11type node32[K comparable, V any] struct {12	son      [2]*node32[K, V]13	priority uint14	key      K15	value    V16	subSize  int17}18 19func (o *node32[K, V]) size() int {20	if o != nil {21		return o.subSize22	}23	return 024}25 26func (o *node32[K, V]) maintain() {27	o.subSize = 1 + o.son[0].size() + o.son[1].size()28}29 30func (o *node32[K, V]) rotate(d int) *node32[K, V] {31	x := o.son[d^1]32	o.son[d^1] = x.son[d]33	x.son[d] = o34	o.maintain()35	x.maintain()36	return x37}38 39type treap32[K comparable, V any] struct {40	rd         uint41	root       *node32[K, V]42	comparator func(a, b K) int43}44 45func (t *treap32[K, V]) fastRand() uint {46	t.rd ^= t.rd << 1347	t.rd ^= t.rd >> 1748	t.rd ^= t.rd << 549	return t.rd50}51 52func (t *treap32[K, V]) size() int   { return t.root.size() }53func (t *treap32[K, V]) empty() bool { return t.size() == 0 }54 55func (t *treap32[K, V]) _put(o *node32[K, V], key K, value V) *node32[K, V] {56	if o == nil {57		o = &node32[K, V]{priority: t.fastRand(), key: key, value: value}58	} else {59		c := t.comparator(key, o.key)60		if c == 0 {61			o.value = value62		} else {63			d := 064			if c > 0 {65				d = 166			}67			o.son[d] = t._put(o.son[d], key, value)68			if o.son[d].priority > o.priority {69				o = o.rotate(d ^ 1)70			}71		}72	}73	o.maintain()74	return o75}76 77func (t *treap32[K, V]) put(key K, value V) { t.root = t._put(t.root, key, value) }78 79func (t *treap32[K, V]) _delete(o *node32[K, V], key K) *node32[K, V] {80	if o == nil {81		return nil82	}83	if c := t.comparator(key, o.key); c != 0 {84		d := 085		if c > 0 {86			d = 187		}88		o.son[d] = t._delete(o.son[d], key)89	} else {90		if o.son[1] == nil {91			return o.son[0]92		}93		if o.son[0] == nil {94			return o.son[1]95		}96		d := 097		if o.son[0].priority > o.son[1].priority {98			d = 199		}100		o = o.rotate(d)101		o.son[d] = t._delete(o.son[d], key)102	}103	o.maintain()104	return o105}106 107func (t *treap32[K, V]) delete(key K) { t.root = t._delete(t.root, key) }108 109func (t *treap32[K, V]) lowerBoundIndex(key K) (kth int) {110	for o := t.root; o != nil; {111		c := t.comparator(key, o.key)112		if c < 0 {113			o = o.son[0]114		} else if c > 0 {115			kth += o.son[0].size() + 1116			o = o.son[1]117		} else {118			kth += o.son[0].size()119			break120		}121	}122	return123}124 125func (t *treap32[K, V]) kth(k int) (o *node32[K, V]) {126	for o = t.root; o != nil; {127		leftSize := o.son[0].size()128		if k < leftSize {129			o = o.son[0]130		} else {131			k -= leftSize + 1132			if k < 0 {133				break134			}135			o = o.son[1]136		}137	}138	return139}140 141type vec32 struct{ x, y int }142 143func (a vec32) dot(b vec32) int { return a.x*b.x + a.y*b.y }144 145func cf932F(in io.Reader, out io.Writer) {146	var n int147	Fscan(in, &n)148	a := make([]int, n)149	for i := range a {150		Fscan(in, &a[i])151	}152	b := make([]int, n)153	for i := range b {154		Fscan(in, &b[i])155	}156	g := make([][]int, n)157	for range n - 1 {158		var v, w int159		Fscan(in, &v, &w)160		v--161		w--162		g[v] = append(g[v], w)163		g[w] = append(g[w], v)164	}165 166	det := func(x1, y1, x2, y2 int) int {167		v := new(big.Int).Mul(big.NewInt(int64(x1)), big.NewInt(int64(y2)))168		w := new(big.Int).Mul(big.NewInt(int64(y1)), big.NewInt(int64(x2)))169		return v.Cmp(w)170	}171	remove := func(t *treap32[int, int], i int) bool {172		if i <= 0 || i+1 >= t.size() {173			return false174		}175		pre := t.kth(i - 1)176		cur := t.kth(i)177		nxt := t.kth(i + 1)178		if det(cur.key-pre.key, cur.value-pre.value, nxt.key-pre.key, nxt.value-pre.value) <= 0 {179			t.delete(cur.key)180			return true181		}182		return false183	}184	contains := func(t *treap32[int, int], x, y int) bool {185		i := t.lowerBoundIndex(x)186		if i == t.size() {187			return false188		}189		cur := t.kth(i)190		if cur.key == x {191			return y >= cur.value192		}193		if i == 0 {194			return false195		}196		pre := t.kth(i - 1)197		return det(cur.key-pre.key, cur.value-pre.value, x-pre.key, y-pre.value) >= 0198	}199	insert := func(t *treap32[int, int], x, y int) {200		if contains(t, x, y) {201			return202		}203		t.put(x, y)204		idx := t.lowerBoundIndex(x)205		for j := idx + 1; remove(t, j); {206		}207		for j := idx - 1; remove(t, j); j-- {208		}209	}210 211	ans := make([]any, n)212	var dfs func(int, int) *treap32[int, int]213	dfs = func(v, fa int) *treap32[int, int] {214		t := &treap32[int, int]{215			rd:         1,216			comparator: func(a, b int) int { return a - b },217		}218		for _, w := range g[v] {219			if w == fa {220				continue221			}222			tw := dfs(w, v)223			if t.size() < tw.size() {224				t, tw = tw, t225			}226			var f func(*node32[int, int])227			f = func(o *node32[int, int]) {228				if o == nil {229					return230				}231				f(o.son[0])232				insert(t, o.key, o.value)233				f(o.son[1])234			}235			f(tw.root)236		}237		f := 0238		if !t.empty() {239			p := vec32{a[v], 1}240			j := sort.Search(t.size()-1, func(j int) bool {241				q := t.kth(j)242				q2 := t.kth(j + 1)243				return p.dot(vec32{q.key, q.value}) < p.dot(vec32{q2.key, q2.value})244			})245			q := t.kth(j)246			f = p.dot(vec32{q.key, q.value})247		}248		ans[v] = f249		insert(t, b[v], f)250		return t251	}252	dfs(0, -1)253	Fprintln(out, ans...)254}255 256//func main() { cf932F(bufio.NewReader(os.Stdin), os.Stdout) }257