은하의 지루한 행성 쌍

아주 먼 옛날, 멀고 먼 은하에 행성 $N$개가 있었다. 행성 사이에는 성간 항로 $N-1$개가 있었고, 이 항로만으로 모든 행성이 직접 또는 간접으로 이어져 있었다. 즉, 행성과 항로는 트리를 이룬다. 각 항로에는 그 항로의 호기심을 나타내는 정수가 하나씩 붙어 있다.

두 행성 $A$, $B$의 쌍이 다음 세 조건을 모두 만족하면 지루한 쌍이라고 한다.

• $A$와 $B$는 서로 다른 행성이다.
• 항로를 하나 이상 지나 $A$에서 $B$로 갈 수 있다.
• 그 경로에 있는 모든 항로의 호기심을 비트 단위 XOR한 값이 $0$이다.

쌍 $(A, B)$와 쌍 $(B, A)$는 같은 쌍으로 센다.

세월이 흘러 지금은 사악한 황제가 은하를 다스린다. 황제는 포스로 모든 항로를 정해진 순서대로 파괴하기로 했다. 파괴가 시작되기 전과 항로를 하나씩 파괴한 뒤마다 지루한 쌍이 몇 개인지 구하여라.

첫째 줄에 행성의 수 $N$이 주어진다. ($1 \le N \le 100\,000$)

다음 $N-1$개 줄에는 항로 하나를 나타내는 정수 $A_i$, $B_i$, $Z_i$가 공백으로 구분되어 주어진다. 이는 행성 $A_i$와 행성 $B_i$가 호기심이 $Z_i$인 항로로 직접 이어져 있다는 뜻이다. ($1 \le A_i, B_i \le N$, $0 \le Z_i \le 1\,000\,000\,000$)

마지막 줄에는 $1$부터 $N-1$까지의 순열이 주어진다. 이 순열의 $i$번째 값이 $j$이면 황제는 $i$번째 단계에서 $j$번째로 입력된 항로를 파괴한다. $N = 1$이면 이 줄에는 아무 수도 주어지지 않는다.

$N$개 줄을 출력한다. $k$번째 줄에는 항로를 정확히 $k-1$개 파괴한 뒤 남은 지루한 쌍의 개수를 출력한다.

첫 번째 예제에서는 파괴 전에 행성 $1$과 행성 $2$의 쌍이 지루한 쌍이다. 항로가 파괴된 뒤에는 두 행성을 잇는 경로가 없다.

두 번째 예제에서는 파괴 전에 쌍 $(1, 3)$이 지루한 쌍이다. 첫 번째 파괴 뒤에도, 두 번째 파괴 뒤에도 행성 $1$과 행성 $3$ 사이를 오갈 수 없고, 남은 어떤 쌍도 지루한 쌍이 아니다.

세 번째 예제에서는 모든 항로의 호기심이 $0$이므로, 경로가 남아 있는 모든 행성 쌍이 지루한 쌍이다.