[北大集训 2021] 小明的树

Luogu

IDLGP8990

Time3000ms

Memory512MB

DifficultyP7

2021O2优化CTT（清华集训/北大集训）

小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \thicksim n$ 的排列 $a_1,a_2,\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。 $n-1$ 次点灯后计数器的值，记为这棵树的答案。一个树是美丽的当前仅当对于每一个被点亮的节点，这个节点子树内的节点都是点亮的。小明认为这个问题太简单了，他觉得应该让树动起来。在初始查询后，他会删掉树中一条边并加上一条边，保证修改后还是一棵树，他想知道每一次修改后将计数器清零后重新点灯并计数，这棵树的答案是多少。 ## Input 第一行两个数 $n,m$ ,表示树的节点数为 $n$，有 $m$ 次修改。接下来 $n-1$ 行，每行 $2$ 个数，表示一条边。下一行 $n-1$ 个数 $a_i$，表示一个 $2 \thicksim n$ 的排列。接下来 $m$ 行每行四个数，$x_1,y_1,x_2,y_2$ 表示断开 $x_1,y_1$ 间的边并连接 $x_2,y_2$，保证数据合法。 ## Output 共 $m+1$ 行，第一行表示初始树的答案。接下来 $m$ 行，表示每次修改后树的答案。 [samples] ## Background CTT2021 D3T1 ## Note - 子任务 $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$。

Samples

Input #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

Output #1

Input #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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[北大集训 2021] 小明的树",
    "description": {
      "content": "小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \\thicksim n$ 的排列 $a_1,a_2,\\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。 他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。 $n-1$ 次点灯后计数器的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8990"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \\thicksim n$ 的排列 $a_1,a_2,\\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。\n\n他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。\n\n$n-1$ 次点灯后计数器的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments