问题 B: 树论（二）
内存限制：256 MB
时间限制：4 S
题面：传统
评测方式：文本比较
上传者：
提交：6
通过：4
题目描述
Yoshinow 又得到了一棵 n 个结点的树，结点的标号为1到n内的整数，Yoshinow突发奇想：
如果把树上的一条边删掉后，一棵树会被划成两棵树T1,T2，从T1的节点编号中选一个数x，
再从T2 的结点编号中选一个数y，gcd(x,y)最大能取到多少？3 因为Yoshinow非常好奇，所
以他想对每条边都询问。
形式化地说：有一棵树G=(V,E),V ={1,2,...,n}，n−1条边E ={(u1,v1),...,(un−1,vn−1)}. 对每条边(ui,vi)(i = 1,...,n−1)，需要回答：将 (ui,vi) 删去后，原树 G 会被分成不连通的 两棵树G1=(V1,E1),G2 = (V2,E2)，此时 maxx∈V1,y∈V2 gcd(x,y) 是多少。
形式化地说：有一棵树G=(V,E),V ={1,2,...,n}，n−1条边E ={(u1,v1),...,(un−1,vn−1)}. 对每条边(ui,vi)(i = 1,...,n−1)，需要回答：将 (ui,vi) 删去后，原树 G 会被分成不连通的 两棵树G1=(V1,E1),G2 = (V2,E2)，此时 maxx∈V1,y∈V2 gcd(x,y) 是多少。
输入格式
第一行一个正整数T，表示测试用例组数，1≤T ≤10.
接下来T 组数据，对每组数据：先输入一个正整数n，表示树的点数，2≤n≤10^6，接下来
n−1 行，第i行包括两个整数ui,vi，表示树上的第i条边为(ui,vi).
保证对所有测试用例，∑n≤5×10^6.
输出格式
对每个测试用例，输出一行n−1个整数，第i个整数表示删除边(ui,vi)后的答案。
注：在这题中你可能需要用到更大的栈空间，C++ 选手可以在 main 函数中加入如下代码，
以防出现栈溢出的错误：
int main() {
int size(256<<20); //256M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
//...
exit(0);
}
int main() {
int size(256<<20); //256M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
//...
exit(0);
}
输入样例 复制
2
3
1 2
2 3
4
1 2
2 3
2 4输出样例 复制
1 1
1 1 2数据范围与提示
两个样例如下图所示：
红边表示询问的边，选取的点x,y 对应地用浅蓝色和橙色标注。在样例中，除了第二棵树的 ans3 以外，其他询问中的无序对{x,y}的选取方式都不唯一。
红边表示询问的边，选取的点x,y 对应地用浅蓝色和橙色标注。在样例中，除了第二棵树的 ans3 以外，其他询问中的无序对{x,y}的选取方式都不唯一。