|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||64 MB||55||21||16||43.243%|
A long time ago in a galaxy far, far away, there were N planets. There were also N − 1 interplanetary paths that connected all the planets (directly or indirectly). In other words, the network of planets and paths formed a tree. Additionally, each path was enumerated with an integer that denoted the curiosity of the path.
A pair of planets A, B is boring if the following holds:
Alas, the times have changed and an evil emperor is ruling the galaxy. He decided to use the Force to destroy all the interplanetary paths in a certain order. Determine the number of boring pairs of planets before the emperor started the destruction and after each destruction.
The first line of input contains the integer N (1 ≤ N ≤ 100 000).
Each of the following N − 1 line contains three integers Ai, Bi, Zi (1 ≤ Ai, Bi ≤ N, 0 ≤ Zi ≤ 1 000 000 000) that denote that planets Ai and Bi are directly connected with a path of curiosity Zi.
The following line of input contains the permutation of the first N − 1 integers that denote the order in which the emperor is destroying the paths. If the ith element of the permutation is j, then the emperor destroyed the path between planets Aj and Bj in the ith step.
The output must contain N lines, the kth line containing the number of boring pairs A, B from the task after the emperor destroyed exactly k − 1 paths.
2 1 2 0 1
3 1 2 4 2 3 4 1 2
1 0 0
4 1 2 0 2 3 0 2 4 0 3 1 2
6 3 1 0
Clarification of the first example: Before the destruction, the path between planets 1 and 2 is boring. After destruction, the path between them doesn’t exist anymore.
Clarification of the second example: Before the destruction, pair of planets (1, 3) is boring. Travel between 1 and 3 is no longer possible after the first and after the second destruction, and none of the remaining pairs of planets is boring.
Clarification of the third example: Notice that in this example each pair of planets with a possible path between them is boring because all paths have the curiosity 0.