結果

問題 No.768 Tapris and Noel play the game on Treeone
コンテスト
ユーザー 草苺奶昔
提出日時 2024-05-03 00:49:57
言語 Go
(1.23.4)
結果
AC  
実行時間 755 ms / 2,000 ms
コード長 8,581 bytes
コンパイル時間 13,517 ms
コンパイル使用メモリ 223,768 KB
実行使用メモリ 33,280 KB
最終ジャッジ日時 2024-11-23 20:41:02
合計ジャッジ時間 23,591 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://nyaannyaan.github.io/library/tree/dynamic-rerooting.hpp

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	yuki768()
}

// No.768 Tapris and Noel play the game on Treeone
// https://yukicoder.me/problems/no/768
func yuki768() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int32
	fmt.Fscan(in, &n)
	D := NewDynamicRerooting(n, make([]Info, n))
	for i := int32(0); i < n-1; i++ {
		var u, v int32
		fmt.Fscan(in, &u, &v)
		u, v = u-1, v-1
		D.AddEdge(u, v)
	}

	var res []int32
	for i := int32(0); i < n; i++ {
		q := D.QueryAll(i)
		var u int32
		if q.v != 0 {
			u = q.u1
		} else {
			u = q.u0
		}
		if u == 0 {
			res = append(res, i+1)
		}
	}

	fmt.Fprintln(out, len(res))
	for _, v := range res {
		fmt.Fprintln(out, v)
	}
}

type Path = struct{ v, u0, u1 int32 }
type Point = int32
type Info = int32

func vertex(v Info) Path { return Path{0, 0, 1} }
func addEdge(p Path) Point {
	if p.v != 0 {
		return p.u1 ^ 1
	}
	return p.u0 ^ 1
}
func addVertex(x Point, v Info) Path { return Path{x, 0, 1} }
func rake(x, y Point) Point          { return x | y }
func compress(p, c Path) Path {
	res := Path{}
	res.v = c.v
	w0 := p.v | (c.u0 ^ 1)
	if w0 != 0 {
		res.u0 = p.u1
	} else {
		res.u0 = p.u0
	}
	w1 := p.v | (c.u1 ^ 1)
	if w1 != 0 {
		res.u1 = p.u1
	} else {
		res.u1 = p.u0
	}
	return res
}

type DynamicRerooting struct {
	n       int32
	topTree *TopTree
	nodes   []*tNode
}

func NewDynamicRerooting(n int32, info []Info) *DynamicRerooting {
	res := &DynamicRerooting{n: n, topTree: NewTopTree()}
	nodes := make([]*tNode, n)
	for i := int32(0); i < n; i++ {
		nodes[i] = res.topTree.Alloc(info[i])
	}
	res.nodes = nodes
	return res
}

func (dr *DynamicRerooting) AddEdge(u, v int32) {
	dr.topTree.Evert(dr.nodes[u])
	dr.topTree.Link(dr.nodes[u], dr.nodes[v])
}

func (dr *DynamicRerooting) RemoveEdge(u, v int32) {
	dr.topTree.Evert(dr.nodes[u])
	dr.topTree.Cut(dr.nodes[v])
}

func (dr *DynamicRerooting) GetInfo(u int32) Info {
	return dr.nodes[u].info
}

func (dr *DynamicRerooting) SetInfo(u int32, info Info) {
	dr.topTree.SetKey(dr.nodes[u], info)
}

func (dr *DynamicRerooting) QueryAll(root int32) Path {
	return dr.topTree.QueryAll(dr.nodes[root])
}

func (dr *DynamicRerooting) QuerySubtree(root, u int32) Path {
	return dr.topTree.QuerySubtree(dr.nodes[root], dr.nodes[u])
}

type tNode struct {
	l, r, p          *tNode
	info             Info
	key, sum, revSum Path
	light, belong    *sNode
	rev              bool
}

func newTNode(info Info) *tNode {
	return &tNode{info: info}
}

func (tn *tNode) IsRoot() bool {
	return tn.p == nil || (tn.p.l != tn && tn.p.r != tn)
}

type TopTree struct {
	splay *splayTreeforDashedEdge
}

func NewTopTree() *TopTree { return &TopTree{splay: newSplayTreeforDashedEdge()} }

func (tt *TopTree) Link(child, parent *tNode) {
	tt._expose(parent)
	tt._expose(child)
	child.p = parent
	parent.r = child
	tt._update(parent)
}

func (tt *TopTree) Cut(child *tNode) {
	tt._expose(child)
	parent := child.l
	child.l = nil
	parent.p = nil
	tt._update(child)
}

func (tt *TopTree) Evert(t *tNode) {
	tt._expose(t)
	tt._toggle(t)
	tt._push(t)
}

func (tt *TopTree) Alloc(info Info) *tNode {
	t := newTNode(info)
	tt._update(t)
	return t
}

func (tt *TopTree) IsConnected(u, v *tNode) bool {
	tt._expose(u)
	tt._expose(v)
	return u == v || u.p != nil
}

func (tt *TopTree) Lca(u, v *tNode) *tNode {
	if !tt.IsConnected(u, v) {
		return nil
	}
	tt._expose(u)
	return tt._expose(v)
}

func (tt *TopTree) SetKey(t *tNode, info Info) {
	tt._expose(t)
	t.info = info
	tt._update(t)
}

func (tt *TopTree) QueryAll(u *tNode) Path {
	tt.Evert(u)
	return u.sum
}

// TODO: check
func (tt *TopTree) QueryPath(u, v *tNode) Path {
	tt.Evert(u)
	tt._expose(v)
	return v.sum
}

// root为根时,子树u的和.
func (tt *TopTree) QuerySubtree(root, u *tNode) Path {
	tt.Evert(root)
	tt._expose(u)
	l := u.l
	u.l = nil
	tt._update(u)
	res := u.sum
	u.l = l
	tt._update(u)
	return res
}

func (tt *TopTree) _toggle(t *tNode) {
	t.l, t.r = t.r, t.l
	t.sum, t.revSum = t.revSum, t.sum
	t.rev = !t.rev
}

func (tt *TopTree) _rotr(t *tNode) {
	x := t.p
	y := x.p
	tt._push(x)
	tt._push(t)
	x.l = t.r
	if x.l != nil {
		x.l.p = x
	}
	t.r = x
	x.p = t
	tt._update(x)
	tt._update(t)
	t.p = y
	if t.p != nil {
		if y.l == x {
			y.l = t
		}
		if y.r == x {
			y.r = t
		}
	}
}

func (tt *TopTree) _rotl(t *tNode) {
	x := t.p
	y := x.p
	tt._push(x)
	tt._push(t)
	x.r = t.l
	if x.r != nil {
		x.r.p = x
	}
	t.l = x
	x.p = t
	tt._update(x)
	tt._update(t)
	t.p = y
	if t.p != nil {
		if y.l == x {
			y.l = t
		}
		if y.r == x {
			y.r = t
		}
	}
}

func (tt *TopTree) _push(t *tNode) {
	if t.rev {
		if t.l != nil {
			tt._toggle(t.l)
		}
		if t.r != nil {
			tt._toggle(t.r)
		}
		t.rev = false
	}
}

func (tt *TopTree) _pushRev(t *tNode) {
	if t.rev {
		if t.l != nil {
			tt._toggle(t.l)
		}
		if t.r != nil {
			tt._toggle(t.r)
		}
		t.rev = false
	}
}

func (tt *TopTree) _update(t *tNode) {
	var key Path
	if t.light != nil {
		key = addVertex(t.light.sum, t.info)
	} else {
		key = vertex(t.info)
	}
	sum, revSum := key, key
	if t.l != nil {
		sum = compress(t.l.sum, sum)
		revSum = compress(revSum, t.l.revSum)
	}
	if t.r != nil {
		sum = compress(sum, t.r.sum)
		revSum = compress(t.r.revSum, revSum)
	}
	t.key, t.sum, t.revSum = key, sum, revSum
}

func (tt *TopTree) _splay(t *tNode) {
	tt._push(t)
	{
		rot := t
		for !rot.IsRoot() {
			rot = rot.p
		}
		t.belong = rot.belong
		if t != rot {
			rot.belong = nil
		}
	}
	for !t.IsRoot() {
		q := t.p
		if q.IsRoot() {
			tt._pushRev(q)
			tt._pushRev(t)
			if q.l == t {
				tt._rotr(t)
			} else {
				tt._rotl(t)
			}
		} else {
			r := q.p
			tt._pushRev(r)
			tt._pushRev(q)
			tt._pushRev(t)
			if r.l == q {
				if q.l == t {
					tt._rotr(q)
					tt._rotr(t)
				} else {
					tt._rotl(t)
					tt._rotr(t)
				}
			} else {
				if q.r == t {
					tt._rotl(q)
					tt._rotl(t)
				} else {
					tt._rotr(t)
					tt._rotl(t)
				}
			}
		}
	}
}

func (tt *TopTree) _expose(t *tNode) *tNode {
	var rp *tNode
	for cur := t; cur != nil; cur = cur.p {
		tt._splay(cur)
		if cur.r != nil {
			cur.light = tt.splay._insert(cur.light, addEdge(cur.r.sum))
			cur.r.belong = cur.light
		}
		cur.r = rp
		if cur.r != nil {
			tt.splay._splay(cur.r.belong)
			tt._push(cur.r)
			cur.light = tt.splay._erase(cur.r.belong)
		}
		tt._update(cur)
		rp = cur
	}
	tt._splay(t)
	return rp
}

type sNode struct {
	l, r, p  *sNode
	key, sum Point
}

func newSNode(key Point) *sNode {
	return &sNode{key: key, sum: key}
}

type splayTreeforDashedEdge struct{}

func newSplayTreeforDashedEdge() *splayTreeforDashedEdge {
	return &splayTreeforDashedEdge{}
}

func (st *splayTreeforDashedEdge) _rotr(t *sNode) {
	x := t.p
	y := x.p
	x.l = t.r
	if x.l != nil {
		x.l.p = x
	}
	t.r = x
	x.p = t
	st._update(x)
	st._update(t)
	t.p = y
	if t.p != nil {
		if y.l == x {
			y.l = t
		}
		if y.r == x {
			y.r = t
		}
	}
}

func (st *splayTreeforDashedEdge) _rotl(t *sNode) {
	x := t.p
	y := x.p
	x.r = t.l
	if x.r != nil {
		x.r.p = x
	}
	t.l = x
	x.p = t
	st._update(x)
	st._update(t)
	t.p = y
	if t.p != nil {
		if y.l == x {
			y.l = t
		}
		if y.r == x {
			y.r = t
		}
	}
}

func (st *splayTreeforDashedEdge) _update(t *sNode) {
	t.sum = t.key
	if t.l != nil {
		t.sum = rake(t.sum, t.l.sum)
	}
	if t.r != nil {
		t.sum = rake(t.sum, t.r.sum)
	}
}

func (st *splayTreeforDashedEdge) _getRight(t *sNode) *sNode {
	for t.r != nil {
		t = t.r
	}
	return t
}

func (st *splayTreeforDashedEdge) _alloc(v Point) *sNode {
	t := newSNode(v)
	st._update(t)
	return t
}

func (st *splayTreeforDashedEdge) _splay(t *sNode) {
	for t.p != nil {
		q := t.p
		if q.p == nil {
			if q.l == t {
				st._rotr(t)
			} else {
				st._rotl(t)
			}
		} else {
			r := q.p
			if r.l == q {
				if q.l == t {
					st._rotr(q)
					st._rotr(t)
				} else {
					st._rotl(t)
					st._rotr(t)
				}
			} else {
				if q.r == t {
					st._rotl(q)
					st._rotl(t)
				} else {
					st._rotr(t)
					st._rotl(t)
				}
			}
		}
	}
}

func (st *splayTreeforDashedEdge) _insert(t *sNode, v Point) *sNode {
	if t == nil {
		t = st._alloc(v)
		return t
	}
	cur := st._getRight(t)
	z := st._alloc(v)
	st._splay(cur)
	z.p = cur
	cur.r = z
	st._update(cur)
	st._splay(z)
	return z
}

func (st *splayTreeforDashedEdge) _erase(t *sNode) *sNode {
	st._splay(t)
	x := t.l
	y := t.r
	if x == nil {
		t = y
		if t != nil {
			t.p = nil
		}
	} else if y == nil {
		t = x
		t.p = nil
	} else {
		x.p = nil
		t = st._getRight(x)
		st._splay(t)
		t.r = y
		y.p = t
		st._update(t)
	}
	return t
}
0