P8990 [北大集训 2021] 小明的树

CTT2021 D3T1

小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \thicksim n$ 的排列 $a_1,a_2,\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。 他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。 $n-1$ 次点灯后计数器的值，记为这棵树的答案。 一个树是美丽的当前仅当对于每一个被点亮的节点，这个节点子树内的节点都是点亮的。 小明认为这个问题太简单了，他觉得应该让树动起来。 在初始查询后，他会删掉树中一条边并加上一条边，保证修改后还是一棵树，他想知道每一次修改后将计数器清零后重新点灯并计数，这棵树的答案是多少。

无

无

- 子任务 $1$（$10$ 分）：保证满足 $2 \leq n \leq 500000$，$m = 0$。 - 子任务 $2$（$20$ 分）：保证满足 $2 \leq n \leq 8000$，$0 \leq m \leq 8000$。 - 子任务 $3$（$70$ 分）：保证满足 $2 \leq n \leq 500000$，$0\leq m \leq 500000$。