COCI '15 Contest 4 #5 Galaksija

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

A long time ago in a galaxy far, far away, there were N planets. There were also N1 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:

  • A and B are different planets
  • travelling between planet A and B is possible using one or more interplanetary paths
  • binary XOR of the curiosity of all the paths in that travel is equal to 0

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.

Input

The first line of input contains the integer N (1N100000).

Each of the following N1 line contains three integers Ai, Bi, Zi (1Ai,BiN,0Zi1000000000) 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 N1 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.

Output

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 k1 paths.

Scoring

In test cases worth 20% of total points, it will hold N1000.

In test cases worth at least 30% of total points, every path's curiosity will be equal to 0.

Sample Input 1

Copy
2
1 2 0
1

Sample Output 1

Copy
1
0

Explanation for Sample Output 1

Before the destruction, the path between planets 1 and 2 is boring. After destruction, the path between them doesn't exist anymore.

Sample Input 2

Copy
3
1 2 4
2 3 4
1 2

Sample Output 2

Copy
1
0
0

Explanation for Sample Output 2

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.

Sample Input 3

Copy
4
1 2 0
2 3 0
2 4 0
3 1 2

Sample Output 3

Copy
6
3
1
0

Explanation for Sample Output 3

Notice that in this example each pair of planets with a possible path between them is boring because all paths have the curiosity 0.


Comments

There are no comments at the moment.