#978359 (Go) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	草苺奶昔
提出日時	2024-05-01 18:00:41
言語	Go (1.22.1)
結果	AC
実行時間	142 ms / 2,000 ms
コード長	16,250 bytes
コンパイル時間	14,295 ms
コンパイル使用メモリ	220,188 KB
実行使用メモリ	15,616 KB
最終ジャッジ日時	2024-11-21 23:37:31
合計ジャッジ時間	27,745 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	1 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	1 ms 5,248 KB
testcase_22	AC	1 ms 5,248 KB
testcase_23	AC	1 ms 5,248 KB
testcase_24	AC	1 ms 5,248 KB
testcase_25	AC	1 ms 5,248 KB
testcase_26	AC	1 ms 5,248 KB
testcase_27	AC	1 ms 5,248 KB
testcase_28	AC	1 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	1 ms 5,248 KB
testcase_31	AC	1 ms 5,248 KB
testcase_32	AC	1 ms 5,248 KB
testcase_33	AC	1 ms 5,248 KB
testcase_34	AC	1 ms 5,248 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	1 ms 5,248 KB
testcase_37	AC	1 ms 5,248 KB
testcase_38	AC	1 ms 5,248 KB
testcase_39	AC	1 ms 5,248 KB
testcase_40	AC	1 ms 5,248 KB
testcase_41	AC	1 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	1 ms 5,248 KB
testcase_45	AC	1 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	2 ms 5,248 KB
testcase_48	AC	2 ms 5,248 KB
testcase_49	AC	1 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	2 ms 5,248 KB
testcase_52	AC	2 ms 5,248 KB
testcase_53	AC	2 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	2 ms 5,248 KB
testcase_56	AC	1 ms 5,248 KB
testcase_57	AC	2 ms 5,248 KB
testcase_58	AC	2 ms 5,248 KB
testcase_59	AC	1 ms 5,248 KB
testcase_60	AC	2 ms 5,248 KB
testcase_61	AC	2 ms 5,248 KB
testcase_62	AC	2 ms 5,248 KB
testcase_63	AC	12 ms 5,248 KB
testcase_64	AC	4 ms 5,248 KB
testcase_65	AC	8 ms 5,248 KB
testcase_66	AC	7 ms 5,248 KB
testcase_67	AC	3 ms 5,248 KB
testcase_68	AC	7 ms 5,248 KB
testcase_69	AC	9 ms 5,248 KB
testcase_70	AC	5 ms 5,248 KB
testcase_71	AC	3 ms 5,248 KB
testcase_72	AC	10 ms 5,248 KB
testcase_73	AC	5 ms 5,248 KB
testcase_74	AC	9 ms 5,248 KB
testcase_75	AC	6 ms 5,248 KB
testcase_76	AC	2 ms 5,248 KB
testcase_77	AC	6 ms 5,248 KB
testcase_78	AC	11 ms 5,248 KB
testcase_79	AC	11 ms 5,248 KB
testcase_80	AC	9 ms 5,248 KB
testcase_81	AC	12 ms 5,248 KB
testcase_82	AC	11 ms 5,248 KB
testcase_83	AC	120 ms 11,904 KB
testcase_84	AC	113 ms 11,520 KB
testcase_85	AC	71 ms 7,936 KB
testcase_86	AC	98 ms 10,368 KB
testcase_87	AC	107 ms 11,008 KB
testcase_88	AC	17 ms 5,248 KB
testcase_89	AC	117 ms 11,904 KB
testcase_90	AC	76 ms 8,320 KB
testcase_91	AC	58 ms 7,040 KB
testcase_92	AC	31 ms 5,248 KB
testcase_93	AC	99 ms 9,984 KB
testcase_94	AC	87 ms 9,216 KB
testcase_95	AC	85 ms 8,832 KB
testcase_96	AC	110 ms 11,264 KB
testcase_97	AC	50 ms 6,656 KB
testcase_98	AC	110 ms 11,392 KB
testcase_99	AC	67 ms 7,680 KB
testcase_100	AC	118 ms 11,520 KB
testcase_101	AC	28 ms 5,248 KB
testcase_102	AC	15 ms 5,248 KB
testcase_103	AC	31 ms 5,248 KB
testcase_104	AC	43 ms 6,272 KB
testcase_105	AC	93 ms 9,472 KB
testcase_106	AC	55 ms 6,656 KB
testcase_107	AC	117 ms 11,904 KB
testcase_108	AC	116 ms 11,648 KB
testcase_109	AC	92 ms 9,856 KB
testcase_110	AC	84 ms 9,088 KB
testcase_111	AC	90 ms 9,344 KB
testcase_112	AC	41 ms 5,888 KB
testcase_113	AC	81 ms 8,832 KB
testcase_114	AC	53 ms 6,656 KB
testcase_115	AC	18 ms 5,248 KB
testcase_116	AC	62 ms 7,168 KB
testcase_117	AC	40 ms 6,016 KB
testcase_118	AC	110 ms 11,264 KB
testcase_119	AC	68 ms 7,552 KB
testcase_120	AC	108 ms 10,496 KB
testcase_121	AC	35 ms 5,248 KB
testcase_122	AC	60 ms 7,040 KB
testcase_123	AC	1 ms 5,248 KB
testcase_124	AC	142 ms 15,616 KB
testcase_125	AC	142 ms 15,488 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// https://maspypy.github.io/library/graph/unicyclic.hpp
// !Namori Graph 无向图基环树
// !一个有 n 个顶点和 n 条边的“连通”无向图。图中只有一个环。
// 这个图被称为“Namori图”，这是根据一位漫画家的名字而命名的，
// 但在学术界中，正确的称呼是“单环图(Unicyclic)”或“伪森林(Pseudoforest)”。

// 例如：下图是一个无向基环树，其中的边权都是1。
//
//	  0
//	  |
//	  1
//	 / \
//	2   3 - 4 - 5
//	 \ /
//	  6
//
// root: 3
// outEdge: 3-6
// to: [1 3 1 6 3 4 2]
// cycle: [6 2 1 3] (bottom到root的路径)
// directedGraph:
//
//	    3(root)
//	   / \
//	  1   4
//	 / \   \
//	0   2   5
//	     \
//	      6(bottom)
//
// !性质1：点u在所在子树的根节点(在环上)为lca(u, bottom).
//
// !这种维护方法的优势是支持动态修改点权或者边权

package main

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

func main() {
	yuki1254()
	// abc266f()
	// namoriCut()
}

// https://yukicoder.me/problems/no/1254
// 找基环树中的环上的边.
func yuki1254() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

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

	namori := NewNamoriGraph(n, edges)
	res := []int32{}
	for i, e := range edges {
		if namori.InCycle[e.u] && namori.InCycle[e.v] {
			res = append(res, int32(i+1))
		}
	}

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

// https://atcoder.jp/contests/abc266/tasks/abc266_f
// 每次查询基环树中两个点是否由唯一的路径相连.
// 等价于：所在子树的根节点是否相同.
func abc266f() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

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

	var q int32
	fmt.Fscan(in, &q)
	queries := make([][2]int32, q)
	for i := int32(0); i < q; i++ {
		var u, v int32
		fmt.Fscan(in, &u, &v)
		u--
		v--
		queries[i] = [2]int32{u, v}
	}

	namori := NewNamoriGraph(n, edges)
	_, tree := namori.BuildTree()
	root := namori.Root
	bottom := namori.To[root]
	for _, q := range queries {
		u, v := q[0], q[1]
		lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
		if lca1 == lca2 {
			fmt.Fprintln(out, "Yes")
		} else {
			fmt.Fprintln(out, "No")
		}
	}
}

func namoriCut() {
	// https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891
	// 给定一个基环树 q个询问(x,y)
	// 求使得x和y不连通最少需要切掉多少条边
	// 如果两个点都在环上,则答案为2
	// 否则答案为1(两点之间只有唯一的一条路径)

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int32
	fmt.Fscan(in, &n)
	edges := make([]edge, n)
	for i := int32(0); i < n; i++ {
		var a, b int32
		fmt.Fscan(in, &a, &b)
		a, b = a-1, b-1
		edges[i] = edge{a, b, 1}
	}

	G := NewNamoriGraph(n, edges)
	_, tree := G.BuildTree()
	root := G.Root
	bottom := G.To[root]

	var q int32
	fmt.Fscan(in, &q)
	for i := int32(0); i < q; i++ {
		var x, y int32
		fmt.Fscan(in, &x, &y)
		x, y = x-1, y-1
		lca1, lca2 := tree.LCA(x, bottom), tree.LCA(y, bottom)
		if lca1 == lca2 {
			fmt.Fprintln(out, 1)
		} else {
			fmt.Fprintln(out, 2)
		}
	}
}

func demo() {
	edges := []edge{
		{0, 1, 1}, {1, 2, 2}, {1, 3, 3}, {2, 6, 6}, {3, 6, 6}, {3, 4, 4}, {4, 5, 5},
	}
	namori := NewNamoriGraph(7, edges)
	fmt.Println(namori.Root)
	fmt.Println(namori.OutEdgeId)
	fmt.Println(namori.OutCost)
	fmt.Println(namori.To)
	fmt.Println(namori.Cycle)

	directedGraph, tree := namori.BuildTree()
	fmt.Println(directedGraph)
	fmt.Println(namori.Dist(tree, 0, 5))
}

type edge = struct {
	u, v int32
	w    int
}

type neighbor = struct {
	to, eid int32
	weight  int
}

// !无向基环树.
type NamoriGraph struct {
	RawEdges []edge
	RawGraph [][]neighbor

	N         int32
	Root      int32 // 断开outEdge后有向树的根
	OutEdgeId int32 // build后不在树中的边
	OutCost   int
	To        []int32 // !向Root方向移动1步后的结点，Root的To为对应outEdge的另一端
	Cycle     []int32
	InCycle   []bool
}

func NewNamoriGraph(n int32, edges []edge) *NamoriGraph {
	m := int32(len(edges))
	if m != n {
		panic("invalid namori graph")
	}

	graph := make([][]neighbor, n)
	for eid := int32(0); eid < m; eid++ {
		e := &edges[eid]
		u, v, w := e.u, e.v, e.w
		graph[u] = append(graph[u], neighbor{to: v, weight: w, eid: eid})
		graph[v] = append(graph[v], neighbor{to: u, weight: w, eid: eid})
	}

	uf := newUnionFindArraySimple32(n)
	to := make([]int32, n)
	for i := range to {
		to[i] = -1
	}

	root := int32(-1)
	outEdgeId, outCost := int32(-1), -1
	for eid := int32(0); eid < m; eid++ {
		e := &edges[eid]
		u, v, w := e.u, e.v, e.w
		if uf.Union(u, v) {
			continue
		}
		outEdgeId, outCost = eid, w
		root = u
		to[root] = v
		break
	}
	visited := make([]bool, n)
	stack := []int32{root}
	for len(stack) > 0 {
		pre := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		visited[pre] = true
		for _, e := range graph[pre] {
			next, eid := e.to, e.eid
			if visited[next] || eid == outEdgeId {
				continue
			}
			to[next] = pre
			stack = append(stack, next)
		}
	}

	cycle := []int32{to[root]}
	for cycle[len(cycle)-1] != root {
		cycle = append(cycle, to[cycle[len(cycle)-1]])
	}

	inCycle := make([]bool, n)
	for _, v := range cycle {
		inCycle[v] = true
	}

	return &NamoriGraph{
		RawEdges:  edges,
		RawGraph:  graph,
		N:         n,
		Root:      root,
		OutEdgeId: outEdgeId,
		OutCost:   outCost,
		To:        to,
		Cycle:     cycle,
		InCycle:   inCycle,
	}
}

// 断开outEdge, 生成有向树.
func (ng *NamoriGraph) BuildTree() (directedGraph [][]neighbor, tree *Tree) {
	directedGraph = make([][]neighbor, ng.N)
	for eid := int32(0); eid < ng.N; eid++ {
		if eid == ng.OutEdgeId {
			continue
		}
		e := &ng.RawEdges[eid]
		u, v, w := e.u, e.v, e.w
		if ng.To[u] == v {
			u, v = v, u
		}
		directedGraph[u] = append(directedGraph[u], neighbor{to: v, weight: w, eid: eid})
	}
	tree = NewTree(directedGraph)
	tree.Build(ng.Root)
	return
}

// 基环树求距离.
func (ng *NamoriGraph) Dist(tree *Tree, u, v int32) int32 {
	bottom := ng.To[ng.Root]
	// lca为在环上的点
	lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
	distOnCyle := abs32(tree.Depth[lca1] - tree.Depth[lca2])
	distOnCyle = min32(distOnCyle, int32(len(ng.Cycle))-distOnCyle)
	return distOnCyle + tree.Depth[u] + tree.Depth[v] - tree.Depth[lca1] - tree.Depth[lca2]
}

func (ng *NamoriGraph) DistWeighted(tree *Tree, u, v int32) int {
	bottom := ng.To[ng.Root]
	lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
	distOnCycle := abs(tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2])
	distOnCycle = min(distOnCycle, tree.DepthWeighted[bottom]+ng.OutCost-distOnCycle)
	return distOnCycle + tree.DepthWeighted[u] + tree.DepthWeighted[v] - tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2]
}

type unionFindArraySimple32 struct {
	Part int32
	n    int32
	data []int32
}

func newUnionFindArraySimple32(n int32) *unionFindArraySimple32 {
	data := make([]int32, n)
	for i := int32(0); i < n; i++ {
		data[i] = -1
	}
	return &unionFindArraySimple32{Part: n, n: n, data: data}
}

func (u *unionFindArraySimple32) Union(key1, key2 int32) bool {
	root1, root2 := u.Find(key1), u.Find(key2)
	if root1 == root2 {
		return false
	}
	if u.data[root1] > u.data[root2] {
		root1, root2 = root2, root1
	}
	u.data[root1] += u.data[root2]
	u.data[root2] = int32(root1)
	u.Part--
	return true
}

func (u *unionFindArraySimple32) Find(key int32) int32 {
	if u.data[key] < 0 {
		return key
	}
	u.data[key] = u.Find(u.data[key])
	return u.data[key]
}

func (u *unionFindArraySimple32) GetSize(key int32) int32 {
	return -u.data[u.Find(key)]
}

type Tree struct {
	Tree          [][]neighbor // (next, weight)
	Depth         []int32
	DepthWeighted []int
	Parent        []int32
	LID, RID      []int32 // 欧拉序[in,out)
	IdToNode      []int32
	top, heavySon []int32
	timer         int32
}

func NewTree(graph [][]neighbor) *Tree {
	n := int32(len(graph))
	tree := graph
	lid := make([]int32, n)
	rid := make([]int32, n)
	IdToNode := make([]int32, n)
	top := make([]int32, n)   // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
	depth := make([]int32, n) // 深度
	depthWeighted := make([]int, n)
	parent := make([]int32, n)   // 父结点
	heavySon := make([]int32, n) // 重儿子
	for i := range parent {
		parent[i] = -1
	}

	return &Tree{
		Tree:          tree,
		Depth:         depth,
		DepthWeighted: depthWeighted,
		Parent:        parent,
		LID:           lid,
		RID:           rid,
		IdToNode:      IdToNode,
		top:           top,
		heavySon:      heavySon,
	}
}

// root:0-based
//
//	当root设为-1时，会从0开始遍历未访问过的连通分量
func (tree *Tree) Build(root int32) {
	if root != -1 {
		tree.build(root, -1, 0, 0)
		tree.markTop(root, root)
	} else {
		for i := int32(0); i < int32(len(tree.Tree)); i++ {
			if tree.Parent[i] == -1 {
				tree.build(i, -1, 0, 0)
				tree.markTop(i, i)
			}
		}
	}
}

// 返回 root 的欧拉序区间, 左闭右开, 0-indexed.
func (tree *Tree) Id(root int32) (int32, int32) {
	return tree.LID[root], tree.RID[root]
}

// 返回返回边 u-v 对应的 欧拉序起点编号, 1 <= eid <= n-1., 0-indexed.
func (tree *Tree) Eid(u, v int32) int32 {
	if tree.LID[u] > tree.LID[v] {
		return tree.LID[u]
	}
	return tree.LID[v]
}

func (tree *Tree) LCA(u, v int32) int32 {
	for {
		if tree.LID[u] > tree.LID[v] {
			u, v = v, u
		}
		if tree.top[u] == tree.top[v] {
			return u
		}
		v = tree.Parent[tree.top[v]]
	}
}

func (tree *Tree) RootedLCA(u, v int32, root int32) int32 {
	return tree.LCA(u, v) ^ tree.LCA(u, root) ^ tree.LCA(v, root)
}

func (tree *Tree) RootedParent(u int32, root int32) int32 {
	return tree.Jump(u, root, 1)
}

func (tree *Tree) Dist(u, v int32, weighted bool) int {
	if weighted {
		return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]
	}
	return int(tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)])
}

// k: 0-based
//
//	如果不存在第k个祖先，返回-1
//	kthAncestor(root,0) == root
func (tree *Tree) KthAncestor(root, k int32) int32 {
	if k > tree.Depth[root] {
		return -1
	}
	for {
		u := tree.top[root]
		if tree.LID[root]-k >= tree.LID[u] {
			return tree.IdToNode[tree.LID[root]-k]
		}
		k -= tree.LID[root] - tree.LID[u] + 1
		root = tree.Parent[u]
	}
}

// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)
//
//	返回跳到的节点,如果不存在这样的节点,返回-1
func (tree *Tree) Jump(from, to, step int32) int32 {
	if step == 1 {
		if from == to {
			return -1
		}
		if tree.IsInSubtree(to, from) {
			return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
		}
		return tree.Parent[from]
	}
	c := tree.LCA(from, to)
	dac := tree.Depth[from] - tree.Depth[c]
	dbc := tree.Depth[to] - tree.Depth[c]
	if step > dac+dbc {
		return -1
	}
	if step <= dac {
		return tree.KthAncestor(from, step)
	}
	return tree.KthAncestor(to, dac+dbc-step)
}

func (tree *Tree) CollectChild(root int32) []int32 {
	res := []int32{}
	for _, e := range tree.Tree[root] {
		next := e.to
		if next != tree.Parent[root] {
			res = append(res, next)
		}
	}
	return res
}

// 返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.
//
//	!eg:[[2 0] [4 4]] 沿着路径顺序但不一定沿着欧拉序.
func (tree *Tree) GetPathDecomposition(u, v int32, vertex bool) [][2]int32 {
	up, down := [][2]int32{}, [][2]int32{}
	for {
		if tree.top[u] == tree.top[v] {
			break
		}
		if tree.LID[u] < tree.LID[v] {
			down = append(down, [2]int32{tree.LID[tree.top[v]], tree.LID[v]})
			v = tree.Parent[tree.top[v]]
		} else {
			up = append(up, [2]int32{tree.LID[u], tree.LID[tree.top[u]]})
			u = tree.Parent[tree.top[u]]
		}
	}
	edgeInt := int32(1)
	if vertex {
		edgeInt = 0
	}
	if tree.LID[u] < tree.LID[v] {
		down = append(down, [2]int32{tree.LID[u] + edgeInt, tree.LID[v]})
	} else if tree.LID[v]+edgeInt <= tree.LID[u] {
		up = append(up, [2]int32{tree.LID[u], tree.LID[v] + edgeInt})
	}
	for i := 0; i < len(down)/2; i++ {
		down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]
	}
	return append(up, down...)
}

// 遍历路径上的 `[起点,终点)` 欧拉序 `左闭右开` 区间.
func (tree *Tree) EnumeratePathDecomposition(u, v int32, vertex bool, f func(start, end int32)) {
	for {
		if tree.top[u] == tree.top[v] {
			break
		}
		if tree.LID[u] < tree.LID[v] {
			a, b := tree.LID[tree.top[v]], tree.LID[v]
			if a > b {
				a, b = b, a
			}
			f(a, b+1)
			v = tree.Parent[tree.top[v]]
		} else {
			a, b := tree.LID[u], tree.LID[tree.top[u]]
			if a > b {
				a, b = b, a
			}
			f(a, b+1)
			u = tree.Parent[tree.top[u]]
		}
	}

	edgeInt := int32(1)
	if vertex {
		edgeInt = 0
	}

	if tree.LID[u] < tree.LID[v] {
		a, b := tree.LID[u]+edgeInt, tree.LID[v]
		if a > b {
			a, b = b, a
		}
		f(a, b+1)
	} else if tree.LID[v]+edgeInt <= tree.LID[u] {
		a, b := tree.LID[u], tree.LID[v]+edgeInt
		if a > b {
			a, b = b, a
		}
		f(a, b+1)
	}
}

func (tree *Tree) GetPath(u, v int32) []int32 {
	res := []int32{}
	composition := tree.GetPathDecomposition(u, v, true)
	for _, e := range composition {
		a, b := e[0], e[1]
		if a <= b {
			for i := a; i <= b; i++ {
				res = append(res, tree.IdToNode[i])
			}
		} else {
			for i := a; i >= b; i-- {
				res = append(res, tree.IdToNode[i])
			}
		}
	}
	return res
}

// 以root为根时,结点v的子树大小.
func (tree *Tree) SubSize(v, root int32) int32 {
	if root == -1 {
		return tree.RID[v] - tree.LID[v]
	}
	if v == root {
		return int32(len(tree.Tree))
	}
	x := tree.Jump(v, root, 1)
	if tree.IsInSubtree(v, x) {
		return tree.RID[v] - tree.LID[v]
	}
	return int32(len(tree.Tree)) - tree.RID[x] + tree.LID[x]
}

// child 是否在 root 的子树中 (child和root不能相等)
func (tree *Tree) IsInSubtree(child, root int32) bool {
	return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}

// 寻找以 start 为 top 的重链 ,heavyPath[-1] 即为重链底端节点.
func (tree *Tree) GetHeavyPath(start int32) []int32 {
	heavyPath := []int32{start}
	cur := start
	for tree.heavySon[cur] != -1 {
		cur = tree.heavySon[cur]
		heavyPath = append(heavyPath, cur)
	}
	return heavyPath
}

// 结点v的重儿子.如果没有重儿子,返回-1.
func (tree *Tree) GetHeavyChild(v int32) int32 {
	k := tree.LID[v] + 1
	if k == int32(len(tree.Tree)) {
		return -1
	}
	w := tree.IdToNode[k]
	if tree.Parent[w] == v {
		return w
	}
	return -1
}

func (tree *Tree) ELID(u int32) int32 {
	return 2*tree.LID[u] - tree.Depth[u]
}

func (tree *Tree) ERID(u int32) int32 {
	return 2*tree.RID[u] - tree.Depth[u] - 1
}

func (tree *Tree) build(cur, pre, dep int32, dist int) int32 {
	subSize, heavySize, heavySon := int32(1), int32(0), int32(-1)
	for _, e := range tree.Tree[cur] {
		next, weight := e.to, e.weight
		if next != pre {
			nextSize := tree.build(next, cur, dep+1, dist+int(weight))
			subSize += nextSize
			if nextSize > heavySize {
				heavySize, heavySon = nextSize, next
			}
		}
	}
	tree.Depth[cur] = dep
	tree.DepthWeighted[cur] = dist
	tree.heavySon[cur] = heavySon
	tree.Parent[cur] = pre
	return subSize
}

func (tree *Tree) markTop(cur, top int32) {
	tree.top[cur] = top
	tree.LID[cur] = tree.timer
	tree.IdToNode[tree.timer] = cur
	tree.timer++
	heavySon := tree.heavySon[cur]
	if heavySon != -1 {
		tree.markTop(heavySon, top)
		for _, e := range tree.Tree[cur] {
			next := e.to
			if next != heavySon && next != tree.Parent[cur] {
				tree.markTop(next, next)
			}
		}
	}
	tree.RID[cur] = tree.timer
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b

}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func abs32(a int32) int32 {
	if a < 0 {
		return -a
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}