만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리와 케이

시간 제한3초메모리 제한1024 MB

요약
가중치가 있는 트리에서 정점 x로부터 거리가 정확히 d인 모든 정점 번호의 XOR을 구합니다.
난이도

보통10점 중 7점

유형
트리, 분할 정복, 해시맵
정답자
아직 제출이 없습니다

문제

정점이 NN개인 트리가 주어진다. 트리는 방향이 없고 사이클이 없는 연결 그래프이다. 정점은 11부터 NN까지 번호가 매겨져 있고, 각 간선에는 가중치가 있다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • xx dd: 정점 xx에서 거리가 정확히 dd인 정점의 번호를 모두 XOR한 값을 출력한다.

입력

첫째 줄에 NN과 MM이 공백으로 구분되어 주어진다. (1≤N,M≤200 000)(1 \leq N, M \leq 200\,000)

둘째 줄부터 N−1N-1개의 줄에 걸쳐 ii번째 간선이 연결하는 서로 다른 두 정점의 번호 uiu_i, viv_i와 간선의 가중치 wiw_i가 공백으로 구분되어 주어진다. (1≤ui,vi≤N;(1 \leq u_i, v_i \leq N; ui≠vi;u_i \neq v_i; 1≤wi≤1 000 000 000)1 \leq w_i \leq 1\,000\,000\,000)

입력된 그래프가 트리임이 보장된다.

다음 MM개의 줄에는 쿼리 정점 번호 xix_i와 거리 did_i가 한 줄에 하나씩 공백으로 구분되어 주어진다. (1≤xi≤N;(1 \leq x_i \leq N; 0≤di≤1015)0 \leq d_i \leq 10^{15})

출력

각 쿼리의 결과를 입력 순서대로 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    6 4
6 2 2
1 4 2
2 3 1
2 4 4
4 5 2
2 6
3 5
4 2
4 4
    예상 출력
    4
4
4
2

  2. 예제 2

    입력
    19 4
8 7 1
9 7 1
7 6 1
11 10 1
12 10 1
10 6 1
6 1 1
2 1 1
1 3 1
3 4 1
3 5 1
1 13 1
13 14 1
14 15 1
13 16 1
16 17 1
16 18 1
16 19 1
6 4
1 3
10 3
14 3
    예상 출력
    31
25
13
23