| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1406
zry和他的的灯泡们
Time Limit: 3000ms
Memory Limit: 65536kb Description
zry有一个收集灯泡的习惯，他把灯泡的阴极都共地，阳极连成一颗树，这样的话，他只要在任意一个灯泡的阳极加上合适的电压，所有灯泡都能亮起来。不幸的是，有一对灯泡之间的阳极连线断掉了，这样的话，这颗灯泡树就还有一部分能亮，一部分不能亮了。zry想知道如果他在任意一个灯泡的阳极上加电压，这一对灯泡的哪一个会亮？
Input
首先是一个正整数T(1<=T<=10)表示测试数据的组数。对于每一组测试数据： 第一行是一个整数n，q（3<=n，q<=100000)，n表示灯泡总数，q表示查询个数。 接下来的n-1行，每行2个整数x，y（1<=x,y<=n)，表示灯泡x和灯泡y的阳极相连。（数据保证合法，是一棵树） 接下来的q行，每行3个整数，a，b，c（1<=a，b，c<=n,数据保证合法，灯泡a和灯泡b之间有边且a不等于b）表示灯泡a和灯泡b之间阳极连线断开的话，在c的阳极加一个电压。 Output
每个查询之间相互独立，对于每个查询输出a和b哪一个会亮，输出a或者b即可。
Sample Input
1 3 1 1 2 2 3 1 2 3 Sample Output
2 |