P12809 [HackerEarth] oliver and the game 3
普及
题目描述

Oliver and Bob are best friends. They have spent their entire childhood in the beautiful city of Byteland. The people of Byteland live happily along with the King.
The city has a unique architecture with total N houses. The King's Mansion is a very big and beautiful bungalow having address = 1. Rest of the houses in Byteland have some unique address, (say A), are connected by roads and there is always a unique path between any two houses in the city. Note that the King's Mansion is also included in these houses.

Oliver and Bob have decided to play Hide and Seek taking the entire city as their arena. In the given scenario of the game, it's Oliver's turn to hide and Bob is supposed to find him.
Oliver can hide in any of the houses in the city including the King's Mansion. As Bob is a very lazy person, for finding Oliver, he either goes towards the King's Mansion (he stops when he reaches there), or he moves away from the Mansion in any possible path till the last house on that path.

Oliver runs and hides in some house (say X) and Bob is starting the game from his house (say Y). If Bob reaches house X, then he surely finds Oliver.

Given Q queries, you need to tell Bob if it is possible for him to find Oliver or not.

The queries can be of the following two types:
0 X Y : Bob moves towards the King's Mansion.
1 X Y : Bob moves away from the King's Mansion

INPUT :
The first line of the input contains a single integer N, total number of houses in the city.
Next N-1 lines contain two space separated integers A and B denoting a road between the houses at address A and B.
Next line contains a single integer Q denoting the number of queries.
Following Q lines contain three space separated integers representing each query as explained above.

OUTPUT :
Print "YES" or "NO" for each query depending on the answer to that query.

CONSTRAINTS :
1 ≤ N ≤ 10^5
1 ≤ A,B ≤ N
1 ≤ Q ≤ 5*10^5
1 ≤ X,Y ≤ N

NOTE :
Large Input size. Use printf scanf or other fast I/O methods.

SAMPLE INPUT
9
1 2
1 3
2 6
2 7
6 9
7 8
3 4
3 5
5
0 2 8
1 2 8
1 6 5
0 6 5
1 9 1

SAMPLE OUTPUT
YES
NO
NO
NO
YES

Explanation

Query 1
Bob goes from 8 towards 1 meeting 2 in the path.
Query 2
Bob goes from 8 away from 1 and never meets 2.
Query 3
Bob goes from 5 away from 1 and never meets 6.
Query 4
Bob goes from 5 towards 1 and never meets 6.
Query 5
Bob goes from 1 away from 1 and meets finds Oliver at 9.
he can take the following two paths
1 -> 2 -> 6 -> 9
OR
1 -> 2 -> 7 -> 8
9 appears in atleast one of them

输入格式

见题面

输出格式

见题面

样例输入
200 34 138 160 40 109 52 133 196 49 141 167 199 156 128 100 184 192 66 118 177 30 185 137 188 169 182 11 131 131 112 154 106 65 42 163 68 88 39 28 133 7 180 42 78 39 152 140 108 125 190 90 81 173 62 199 46 48 28 105 70 119 156 21 30 186 122 171 93 38 193 27 20 108 14 49 71 198 48 60 174 159 178 196 53 120 41 8 173 170 75 13 119 88 145 104 82 182 89 82 183 155 140 65 73 24 51 200 166 99 86 74 49 110 94 84 149 138 139 6 77 39 104 88 102 134 57 87 132 145 7 189 186 42 90 63 110 194 126 172 175 114 158 16 24 157 103 17 136 98 163 197 85 146 44 77 91 121 101 44 35 183 121 167 179 76 9 20 162 91 98 41 67 58 25 103 31 165 144 164 76 85 160 181 65 89 32 166 4 56 47 120 54 105 97 191 100 5 134 12 27 139 189 67 95 68 17 118 200 1 170 158 129 10 33 153 26 141 197 138 16 86 130 32 192 7 59 19 10 25 36 174 61 61 142 62 29 104 118 66 117 83 84 43 45 144 176 51 18 113 6 57 8 52 13 136 96 95 12 126 58 18 37 31 5 56 113 150 164 64 127 54 60 151 63 93 116 1 88 100 105 115 168 122 137 117 172 190 43 195 87 162 159 73 143 149 109 26 171 48 153 33 151 80 15 72 148 60 157 167 120 82 181 96 187 188 74 112 80 9 34 173 69 62 72 75 123 160 125 35 22 92 56 59 107 70 135 50 146 187 23 132 169 134 198 107 154 71 11 193 111 124 3 143 195 39 19 175 124 76 99 123 167 46 83 65 115 89 191 97 150 81 50 161 155 116 114 179 21 69 161 55 2 127 79 23 64 168 38 183 194 79 55 184 92 40 147 53 165 200 1 92 15 0 139 51 0 60 39 1 102 103 0 24 111 0 64 184 1 122 144 1 85 131 1 160 74 1 108 109 1 199 93 1 124 177 0 21 30 0 131 144 1 4 81 0 82 19 1 181 171 1 103 120 1 3 33 0 190 186 1 95 99 1 167 134 0 165 198 0 166 22 0 22 28 0 112 119 0 149 109 0 195 71 1 199 103 0 34 164 0 115 107 0 152 19 0 178 33 0 45 144 1 53 5 0 173 157 1 57 196 1 168 82 0 38 104 1 108 98 1 161 187 0 101 194 0 27 45 0 113 62 1 141 173 1 23 92 1 15 144 1 143 180 1 87 180 1 175 117 1 10 101 0 39 143 1 18 169 0 88 194 1 199 142 0 5 157 0 3 32 1 67 152 0 84 184 0 118 194 1 27 166 0 50 55 1 69 157 1 76 195 0 22 145 1 27 151 0 37 138 1 121 81 1 106 82 0 90 23 1 82 145 1 148 5 0 172 94 1 89 39 0 21 142 1 10 101 0 98 86 1 192 163 0 76 195 1 40 187 0 157 27 0 80 24 0 60 162 1 8 123 0 35 50 0 127 3 0 69 159 1 177 101 1 17 43 0 126 175 1 98 77 0 71 183 0 29 103 0 4 44 1 144 165 1 174 61 1 97 74 1 159 117 1 30 144 1 58 126 1 100 82 1 67 120 1 170 124 0 144 8 1 32 9 1 78 85 1 196 69 0 135 141 1 108 161 1 170 101 0 139 200 0 122 154 1 36 90 1 36 44 1 62 60 1 149 109 1 49 76 0 83 114 0 71 188 0 47 40 0 158 96 0 51 100 0 25 175 0 69 57 1 56 86 0 152 101 1 156 128 1 167 1 0 44 23 1 28 134 0 118 90 1 4 118 0 125 131 1 176 175 1 10 112 0 76 89 1 168 91 0 175 196 0 37 130 0 119 158 1 122 34 0 196 198 1 100 168 0 33 175 1 31 123 0 162 19 1 179 60 0 2 23 0 185 165 0 53 72 1 70 5 0 169 180 1 8 162 1 177 194 0 96 113 0 3 23 0 112 9 1 39 88 1 6 99 0 93 161 1 62 120 0 154 17 1 52 13 0 20 159 0 46 118 1 26 146 1 118 182 0 115 59 0 169 44 1 191 182 0 149 174 1 124 2 1 185 199 0 155 69 1 193 59 1 162 127 1 177 152 0 97 136 1 52 13 1 109 26 1 196 57 0 64 68 1 198 8 1 107 198 1 44 42 0 141 16 1 137 189 0 200 126 0 162 95 1 12 63 1 152 183 0 46 26 0 21 30 0 141 138 0 114 140 1 176 42 0 86 85 1 146 99 1 16 34 0 114 187
样例输出
NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO YES NO NO NO YES NO YES YES YES NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO YES YES YES NO NO NO NO NO NO YES NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO YES NO YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO NO NO YES NO