Задача №113575. Галактический апокалипсис
Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:
1. A и B - различные планеты.
2. В действующей сети межпланетных магистралей существует путь между A и B .
3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.
Ныне в галактике правит злой император, и он планирует использовать Силу, чтобы уничтожить все межпланетные магистрали в определенном порядке. Для того, чтобы спасти вселенную от гибели, вам необходимо определить количество пар скучных планет и после каждого разрушения вновь подсчитывать эту величину.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).
Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.
Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.
2 1 2 0 1
1 0
3 1 2 4 2 3 4 1 2
1 0 0
4 1 2 0 2 3 0 2 4 0 3 1 2
6 3 1 0