| 166 | } |
| 167 | |
| 168 | public static void main(String[] args) throws IOException { |
| 169 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); |
| 170 | StreamTokenizer in = new StreamTokenizer(br); |
| 171 | PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); |
| 172 | in.nextToken(); |
| 173 | n = (int) in.nval; |
| 174 | in.nextToken(); |
| 175 | m = (int) in.nval; |
| 176 | in.nextToken(); |
| 177 | root = (int) in.nval; |
| 178 | for (int i = 1, u, v; i < n; i++) { |
| 179 | in.nextToken(); |
| 180 | u = (int) in.nval; |
| 181 | in.nextToken(); |
| 182 | v = (int) in.nval; |
| 183 | addEdge(u, v); |
| 184 | addEdge(v, u); |
| 185 | } |
| 186 | dfs3(); // dfs3() 等同于 dfs1(root, 0)，调用迭代版防止爆栈 |
| 187 | dfs4(); // dfs4() 等同于 dfs2(root, root)，调用迭代版防止爆栈 |
| 188 | for (int i = 1, a, b; i <= m; i++) { |
| 189 | in.nextToken(); |
| 190 | a = (int) in.nval; |
| 191 | in.nextToken(); |
| 192 | b = (int) in.nval; |
| 193 | out.println(lca(a, b)); |
| 194 | } |
| 195 | out.flush(); |
| 196 | out.close(); |
| 197 | br.close(); |
| 198 | } |
| 199 | |
| 200 | } |