Informatica Online Judge

  서현중로#1 [2360 / 0938]

Time Limit(Test case) : 1500 (ms)
Number of users who solved : 17   Total Tried : 18


The Champion of this Problem (C++) : gs17078 - ms / 837byte
My Best Submission (C++) : N/A

[35th 고동현 (gs17003)]
Writer ID : [gs17003]

Background

부동산 사기로 큰 돈을 번 민제는 삶의 광명을 찾기 위해 청주로 내려갔다. 살기 좋은 장소를 찾던 중 민제는 서현중로라는 곳을 발견했다. 놀랍게도 서현중로에는 N개의 동이 존재하는 아파트 단지가 있었는데 동끼리는 총 N-1개의 길로 이어져 있고 서로 다른 동끼리는 모두 이 길을 통해 이동할 수 있다. 또한 각 동에는 1부터 N까지의 숫자가 매겨져 있다. 민제는 이 아파트 단지를 통으로 구입하여 선량한 청주 시민들에게 전세를 주며 사기를 치려고 한다. 청주 시민들에게 민제는 s_i동부터 e_i 동까지 세를 내어 줄것이다(1<=s_i<=e_i<=N). 또한 민제는 이 아파트 단지를 구입한 이후 모든 길에 암호 w_i를 부여하였다(0<=w_i<=1e18). s_i 동부터 e_i 동까지 입주를 한 청주 시민들은 민제에게 사기를 당한것을 알고 굉장히 분노했다. 하지만 민제가 모든 길에 암호를 걸어 놓아서 동끼리 이동할 수가 없어 경찰에 신고를 할 수 없었다. 그런데 주민들은 곧 놀라운 사실을 알아냈다. 바로 두 동을 잇는 길의 가중치를 모두 xor한 값이 0이 되면 두 동 사이를 이동할 수 있다는 사실이다. 주민들이 서로 만나면 민제를 신고를 할 것이다. 즉 s_i이상 e_i이하의 임의의 두 동의 주민들이 만나면 민제를 신고할 것이다. 그렇다면 민제는 감옥에 가야 한다. Q개의 s_i 와 e_i가 주어질 때 민제가 사기가 성공하면 YES, 실패하면 NO를 출력하시오. 이 문제를 해결해 선량한 청주 시민들을 도와주자.

Input

첫째줄에 동의 개수 N이 주어진다.
두 번째 줄부터 N번째 줄까지 동과 동을 잇는 길의 정보 a_i, b_i, w가 주어진다. 이 의미는 a_i동과 b_i를 잇는 길이 존재하고 이 길의 암호는 w_i라는 뜻이다. (1<=a_i,b_i<=N, 0<=w_i<=1e18)
N+1번째 줄에는 민제가 사기 칠 횟수 Q가 주어진다.
N+2번째 줄부터 다음 Q줄에는 민제가 세를 내줄 동에 대한 정보 s_i, e_i가 주어진다. (1<=s_i<=e_i<=N)

[Subtask-Info]
Subtask #1 1<=N<=1000, 1<=Q<=1,000
Subtask #2 1<=N<=100,000, 1<=Q<=100,000
Subtask #3 1<=N<=500,000, 1<=Q<=500,000

Output

민제가 청주 시민들에게 사기를 칠 때마다 성공하면 YES, 실패하면 NO를 출력하시오.

IO Example

Input
5
1 2 1
1 3 2
2 4 1
2 5 2
3
1 4
2 5
2 3

Output
NO
YES
YES

첫 번째 사기에서는 1동에 사는 주민과 4동에 사는 주민들이 만날 수 있으므로 민제의 사기는 실패한다.
하지만 두 번째와 세 번째 에서는 주민들이 만나지 못하므로 민제의 사기는 성공한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]