## COCI '15 Contest 4 #5 Galaksija

View as PDF

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

Problem types

A long time ago in a galaxy far, far away, there were planets. There were also 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 is boring if the following holds:

• and are different planets
• travelling between planet and 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 .

Each of the following line contains three integers , , that denote that planets and are directly connected with a path of curiosity .

The following line of input contains the permutation of the first integers that denote the order in which the emperor is destroying the paths. If the element of the permutation is , then the emperor destroyed the path between planets and in the step.

#### Output

The output must contain lines, the line containing the number of boring pairs from the task after the emperor destroyed exactly paths.

#### Scoring

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

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

#### Sample Input 1

2
1 2 0
1

#### Sample Output 1

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

3
1 2 4
2 3 4
1 2

#### Sample Output 2

1
0
0

#### Explanation for Sample Output 2

Before the destruction, pair of planets 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

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

#### Sample Output 3

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.