Please note the UNUSUAL MEMORY LIMIT of this problem.
BaoBao has a tree with $$$n$$$ vertices. Initially, all edges of the tree are black. BaoBao likes painting and counting in the tree, so he will perform $$$(n - 1)$$$ painting operations. For the $$$i$$$-th operation, he will paint the $$$q_i$$$-th edge red. It's obvious that after all operations, all edges will become red.
Your task is to calculate how many simple paths in the tree contain exactly $$$k$$$ black edges after each operation. Note that we consider the simple path from vertex $$$u$$$ to $$$v$$$ and from vertex $$$v$$$ to $$$u$$$ to be the same path.
Recall that a simple path is a path that does not go through the same edge multiple times.
There is only one test case in each test file.
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2\leq n\leq 2 \times 10^5$$$, $$$1\leq k\leq 10$$$) indicating the number of vertices in the tree and the number of black edges we count for paths.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) indicating that the $$$i$$$-th edge in the tree connects vertices $$$u_i$$$ and $$$v_i$$$.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains an integer $$$q_i'$$$ ($$$1 \leq q_i' \lt n$$$), indicating the encoded index of the $$$i$$$-th edge BaoBao paints. The real value of $$$q_i$$$ is equal to $$$((q_i'+a_{i-1}) \bmod (n-1))+1$$$, where $$$a_{i-1}$$$ is the answer to the $$$(i-1)$$$-th query. Specifically, we define $$$a_0$$$ as the number of simple paths in the tree that contain exactly $$$k$$$ black edges before BaoBao paints. With the encoded queries, you're forced to calculate the answer to each query before processing the next one. It's guaranteed that $$$q_1, q_2, \dots, q_{n-1}$$$ is a permutation of $$$1, 2, \dots, n-1$$$.
Output $$$(n - 1)$$$ lines where the $$$i$$$-th line contains an integer indicating the number of simple paths with exactly $$$k$$$ black edges after the $$$i$$$-th operation.
6 1 4 6 4 2 4 3 5 6 1 2 4 2 1 2 3
5 7 8 8 0
6 2 4 6 4 2 4 3 5 6 1 2 2 5 5 4 3
5 4 2 0 0
For the first sample test case, the real values of $$$q_1, q_2, q_3, q_4, q_5$$$ are $$$5, 3, 4, 1, 2$$$, respectively. The tree after the first two operations is shown on the left. Black edges are represented with thinner lines, while red edges are represented with thicker lines.
Let $$$u \to v$$$ be the simple path from vertex $$$u$$$ to $$$v$$$. The simple paths containing exactly one black edge are: $$$1 \to 3$$$, $$$1 \to 4$$$, $$$2 \to 3$$$, $$$2 \to 4$$$, $$$3 \to 6$$$, $$$4 \to 6$$$, $$$5 \to 6$$$.
For the second sample test case, the real values of $$$q_1, q_2, q_3, q_4, q_5$$$ are $$$3, 1, 5, 2, 4$$$, respectively. The tree after the first three operations is shown on the right.
The simple paths containing exactly two black edges are: $$$1 \to 5$$$, $$$2 \to 5$$$.
