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 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:

  • 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.


The first line of input contains the integer N (1 \le N \le 100\,000).

Each of the following N-1 line contains three integers A_i, B_i, Z_i (1 \le A_i, B_i \le N, 0 \le Z_i \le 1\,000\,000\,000) that denote that planets 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 the emperor is destroying the paths. If the i^{th} element of the permutation is j, then the emperor destroyed the path between planets A_j and B_j in the i^{th} step.


The output must contain N lines, the k^{th} line containing the number of boring pairs A, B from the task after the emperor destroyed exactly k-1 paths.


In test cases worth 20% of total points, it will hold N \le 1\,000.

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

Sample Input 1

1 2 0

Sample Output 1


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

1 2 4
2 3 4
1 2

Sample Output 2


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

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

Sample Output 3


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.


There are no comments at the moment.