Codeforces 1528C — Trees of Tranquillity

1package main2 3import (4	"bufio"5	. "fmt"6	"io"7	"time"8)9 10// github.com/EndlessCheng/codeforces-go11type node28 struct {12	lr       [2]*node2813	priority uint14	key      int15}16 17func (o *node28) cmp(b int) int {18	switch {19	case b < o.key:20		return 021	case b > o.key:22		return 123	default:24		return -125	}26}27 28func (o *node28) rotate(d int) *node28 {29	x := o.lr[d^1]30	o.lr[d^1] = x.lr[d]31	x.lr[d] = o32	return x33}34 35type treap28 struct {36	rd   uint37	root *node2838}39 40func (t *treap28) fastRand() uint {41	t.rd ^= t.rd << 1342	t.rd ^= t.rd >> 1743	t.rd ^= t.rd << 544	return t.rd45}46 47func (t *treap28) _put(o *node28, key int) *node28 {48	if o == nil {49		return &node28{priority: t.fastRand(), key: key}50	}51	if d := o.cmp(key); d >= 0 {52		o.lr[d] = t._put(o.lr[d], key)53		if o.lr[d].priority > o.priority {54			o = o.rotate(d ^ 1)55		}56	}57	return o58}59 60func (t *treap28) put(key int) { t.root = t._put(t.root, key) }61 62func (t *treap28) _delete(o *node28, key int) *node28 {63	if o == nil {64		return nil65	}66	if d := o.cmp(key); d >= 0 {67		o.lr[d] = t._delete(o.lr[d], key)68	} else {69		if o.lr[1] == nil {70			return o.lr[0]71		}72		if o.lr[0] == nil {73			return o.lr[1]74		}75		d = 076		if o.lr[0].priority > o.lr[1].priority {77			d = 178		}79		o = o.rotate(d)80		o.lr[d] = t._delete(o.lr[d], key)81	}82	return o83}84 85func (t *treap28) delete(key int) { t.root = t._delete(t.root, key) }86 87func (t *treap28) lowerBound(key int) (lb *node28) {88	for o := t.root; o != nil; {89		switch c := o.cmp(key); {90		case c == 0:91			lb = o92			o = o.lr[0]93		case c > 0:94			o = o.lr[1]95		default:96			return o97		}98	}99	return100}101 102func (t *treap28) prev(key int) (prev *node28) {103	for o := t.root; o != nil; {104		if o.cmp(key) <= 0 {105			o = o.lr[0]106		} else {107			prev = o108			o = o.lr[1]109		}110	}111	return112}113 114func CF1528C(_r io.Reader, _w io.Writer) {115	in := bufio.NewReader(_r)116	out := bufio.NewWriter(_w)117	defer out.Flush()118	rd := uint(time.Now().UnixNano())/2 + 1119 120	var T, n, v int121	for Fscan(in, &T); T > 0; T-- {122		Fscan(in, &n)123		g1 := make([][]int, n)124		g2 := make([][]int, n)125		for w := 1; w < n; w++ {126			Fscan(in, &v)127			v--128			g1[v] = append(g1[v], w)129		}130		for w := 1; w < n; w++ {131			Fscan(in, &v)132			v--133			g2[v] = append(g2[v], w)134		}135 136		l := make([]int, n)137		r := make([]int, n)138		at := make([]int, n+1)139		ts := 0140		var f2 func(int)141		f2 = func(v int) {142			ts++143			l[v] = ts144			at[ts] = v145			for _, w := range g2[v] {146				f2(w)147			}148			r[v] = ts149		}150		f2(0)151 152		ans, sz := 0, 0153		t := &treap28{rd: rd}154		var f func(int)155		f = func(v int) {156			lb := t.lowerBound(l[v])157			if lb == nil || lb.key > r[v] { // 子树没有节点在 t 中158				t.put(l[v])159				sz++160				defer func() { t.delete(l[v]); sz-- }()161				if o := t.prev(l[v]); o != nil {162					if pa := at[o.key]; l[pa] < l[v] && l[v] <= r[pa] { // 有父节点在 t 中163						t.delete(l[pa])164						sz--165						defer func() { t.put(l[pa]); sz++ }()166					}167				}168				if sz > ans {169					ans = sz170				}171			}172			for _, w := range g1[v] {173				f(w)174			}175		}176		f(0)177		Fprintln(out, ans)178	}179}180 181//func main() { CF1528C(os.Stdin, os.Stdout) }182