#2058. 小明的树

    ID: 2058 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest871来源:qoj.ac数据:公开样例并查集

小明的树

小明的树

题目描述

标题: 小明的树 - Problem - QOJ.ac

#3275. 小明的树

Statistics

The problem was used in the following contests:

小明有一棵以 1 为根的 n 个节点的树,树上每一个非根节点上有一盏灯,他有一个 2∼n 的排列 a1,a2....an−1。他还有一个计数器,初始为 0。

他会按照排列依次点亮这 n−1 盏灯,每进行一次点灯操作后,他会检查整个树是否是美丽的,如果是美丽的,计数器会加上此时点灯的节点形成的联通块的个数。

n−1 次点灯后计数器的值,记为这棵树的答案。

一个树是美丽的当前仅当对于每一个被点亮的节点,这个节点子树内的节点都是点亮的。

小明认为这个问题太简单了,他觉得应该让树动起来。

在初始查询后,他会删掉树中一条边并加上一条边,保证修改后还是一棵树,他想知道每一次修改后将计数器清零后重新点灯并计数,这棵树的答案是多少。

输入格式

从标准输入读入数据。

第一行两个数 n,m ,表示树的节点数为 n ,有 m 次修改。

接下来 n−1 行,每行 2 个数,表示一条边。

下一行 n−1 个数 ai,表示一个 2∼n 的排列。

接下来 m 行每行四个数,x1,y1,x2,y2 表示断开 x1,y1 间的边并连接 x2,y2,保证数据合法。

输出格式

输出到标准输出。

共 m+1 行,第一行表示初始树的答案。

接下来 m 行,表示每次修改后树的答案。

样例数据

样例 1 输入

10 10
2 1
3 1
4 2
5 1
6 4
7 6
8 5
9 4
10 1
6 4 2 7 8 9 10 3 5
6 7 10 7
1 5 8 9
1 2 10 8
10 8 7 6
2 4 2 9
8 9 1 5
5 8 8 2
2 9 10 8
10 7 4 10
10 8 8 9

样例 1 输出

13
15
4
6
2
2
10
7
8
8
7

样例 2 输入

10 10
2 1
3 2
4 3
5 4
6 2
7 5
8 7
9 1
10 8
6 8 3 9 2 5 7 10 4 
1 9 3 9
4 5 2 7
2 7 6 7
8 10 10 1
6 7 8 1
3 9 9 8
1 2 7 3
2 3 2 9
8 1 1 7
2 9 2 8

样例 2 输出

3
2
2
1
2
4
4
3
3
3
3

数据范围与提示

  • 子任务1(10 分):保证满足 2≤n≤500000,m=0。
  • 子任务2(20 分):保证满足 2≤n≤8000,0≤m≤8000。
  • 子任务3(70 分):保证满足 2≤n≤500000,0≤m≤500000。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

10 10
2 1
3 1
4 2
5 1
6 4
7 6
8 5
9 4
10 1
6 4 2 7 8 9 10 3 5
6 7 10 7
1 5 8 9
1 2 10 8
10 8 7 6
2 4 2 9
8 9 1 5
5 8 8 2
2 9 10 8
10 7 4 10
10 8 8 9
13
15
4
6
2
2
10
7
8
8
7

样例 2

10 10
2 1
3 2
4 3
5 4
6 2
7 5
8 7
9 1
10 8
6 8 3 9 2 5 7 10 4 
1 9 3 9
4 5 2 7
2 7 6 7
8 10 10 1
6 7 8 1
3 9 9 8
1 2 7 3
2 3 2 9
8 1 1 7
2 9 2 8
3
2
2
1
2
4
4
3
3
3
3