Galaksija
레이팅 미적용의견: 0
\(4^{th}\) round, December \(19^{th}\) 2015
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.
In test cases worth 20% of total points, it will hold \(N\) ⩽1 000.
In test cases worth at least 30% of total points, every path’s curiosity will be equal to 0.
The first line of input contains the integer \(N\) (1 ⩽\(N\) ⩽100 000).
Each of the following \(N - 1\) line contains three integers \(A_{i}\), \(B_{i}\), \(Z_{i}\) (1 ⩽\(A_{i}\), B_{i} ⩽\(N\), 0 ⩽\(Z_{i}\) ⩽
1 000 000 000) that denote that planets \(A@@RISE_MATH_BLOCK_0@@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.
2
1 2 0
1
3
1 2 4
2 3 4
1 2
4
1 2 0
2 3 0
2 4 0
3 1 2output
output
1
0
1
0
0
6
3
1
0Clarification of the first example: Before the destruction, the path between planets 1 and 2 is boring. After
destruction, the path between them doesn’t exist anymore.
Clarification of the second example: 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.
Clarification of the third example: Notice that in this example each pair of planets with a possible path
between them is boring because all paths have the curiosity 0.
평가 및 의견
Galaksija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Galaksija