COCI '15 Contest 4 #5 Galaksija

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.