#P18343. Black Red Tree

Black Red Tree

Black Red Tree

题目描述

给定一棵有 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n,边按输入顺序编号为 1,2,…,n−11,2,\ldots,n-1。最初,所有边都是黑色。

接下来依次进行 n−1n-1 次染色操作,第 ii 次将编号为 qiq_i 的边染成红色。保证每条边恰好被染色一次,因此所有操作结束后,树中的边全部为红色。

每次操作后,求树中恰好经过 kk 条黑边的简单路径数量。红边可以出现在路径中,但不计入黑边数量。路径不能重复经过边;从 uu 到 vv 与从 vv 到 uu 视为同一条路径,只统计一次。

本题的操作编号经过编码,你必须利用上一次的正确答案来解码下一次操作。

输入格式

每个输入文件只有一组测试数据。

第一行包含两个整数 n,kn,k。

接下来 n−1n-1 行,第 ii 行包含两个整数 ui,viu_i,v_i,表示第 ii 条边连接顶点 uiu_i 和 viv_i。这些边构成一棵树。

接下来 n−1n-1 行,第 ii 行包含一个整数 qi′q'_i。实际染色的边编号为

qi=((qi′+ai−1) mod (n−1))+1.q_i=((q'_i+a_{i-1})\bmod(n-1))+1.

其中,aia_i 表示第 ii 次染色后的答案。特别地,a0a_0 是尚未进行任何染色、所有边均为黑色时的答案,并非固定为 00。

保证解码后的 q1,q2,…,qn−1q_1,q_2,\ldots,q_{n-1} 是 1,2,…,n−11,2,\ldots,n-1 的一个排列。输入中的编码值 qi′q'_i 可以重复。

输出格式

输出 n−1n-1 行,第 ii 行输出一个整数 aia_i,表示第 ii 次染色后,恰好经过 kk 条黑边的简单路径数量。

数据范围

  • 2≤n≤2×1052\le n\le 2\times10^5;
  • 1≤k≤101\le k\le10;
  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • 1≤qi′<n1\le q'_i<n;
  • 输入边构成树,解码后的操作编号构成排列。

样例输入 1

6 1
4 6
4 2
4 3
5 6
1 2
4
2
1
2
3

样例输出 1

5
7
8
8
0

样例输入 2

6 2
4 6
4 2
4 3
5 6
1 2
2
5
5
4
3

样例输出 2

5
4
2
0
0

样例说明

两组样例中的染色状态,黑色细线表示黑边,红色粗线表示红边

第一组样例解码后的操作编号依次为 5,3,4,1,25,3,4,1,2。上图左侧是前两次操作后的树,其中黑边用细线、红边用粗线表示。此时恰好包含一条黑边的路径为

$$1\to3,\quad1\to4,\quad2\to3,\quad2\to4,\quad 3\to6,\quad4\to6,\quad5\to6,$$

共 77 条。

第二组样例解码后的操作编号依次为 3,1,5,2,43,1,5,2,4。上图右侧是前三次操作后的树。此时恰好包含两条黑边的路径只有 1→51\to5 和 2→52\to5,共 22 条。