+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- A long time ago in the University of Tehran, there were N buildings. There were also $N-1$ pathways that connected all the buildings (directly or indirectly). In other words, the network of buildings and paths formed a tree. Additionally, each path was enumerated with an integer that denoted the curiosity of the path. A pair of buildings A, B is boring if the following holds: * A and B are different buildings * travelling between building A and B is possible using one or more pathways * binary **XOR** of the curiosity of all the paths in that travel is equal to 0 Unfortunately, times have changed, and an evil dean named Zein is now ruling the department. He decided to use the Force to destroy all the pathways in a **certain order**. Determine the number of boring pairs of buildings before Zein started the destruction and after each destruction. # Input The first line of input contains the integer N. Each of the following $N-1$ line contains three integers $a_i$, $b_i$, $z_i$, that denote that buildings $a_i$ and $b_i$ are directly connected with a path of curiosity $z_i$. The following line of input contains the permutation of the first $N-1$ integers that denote the order in which Zein is destroying the paths. If the $i^{th}$ element of the permutation is j, then Zein destroyed the path between buildings $a_i$ and $b_i$ in the $i^{th}$ step. # Output The output must contain N lines, the $k^{th}$ line containing the number of boring pairs A, B from the task after Zein destroyed exactly $k-1$ paths. # Constraints * $1 \leq N \leq 10^5 $ * $1 \leq a_i,b_i \leq N $ * $0 \leq z_i \leq 10^9 $ # Sample Test Data ## input 1 ``` 3 1 2 5 2 3 5 2 1 ``` ## output 1 ``` 1 0 0 ``` ## input 2 ``` 4 1 2 0 2 3 0 2 4 0 3 1 2 ``` ## output 2 ``` 6 3 1 0 ```

حل سؤال در بانک سؤالات