/* 性质: 1.删除重心后所得的所有子树,节点数不超过原树的1/2,一棵树最多有两个重心 2.树中所有节点到重心的距离之和最小,如果有两个重心,那么他们距离之和相等 3.两个树通过一条边合并,新的重心在原树两个重心的路径上 4.树删除或添加一个叶子结点,重心最多只移动一条边 5.一棵树最多有两个重心,且相邻 思路: (1)如果只有一个重心,那么直接删除跟重心相连的点,然后加回去就好了,这样还是只有一个重心 (2)如果有两个重心,那么在其中一个重心上找到一个与这个重心直接相连的点且不是另外一个重心, 删除这个点与重心之间的边,将这个点连上另外一个重心就好了 */ #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; const int maxn=1e5+100; vector<ll>g[100005]; ll siz[100005]; //表示以i为根节点的子树节点个数 //siz[i]=求和(siz[i的儿子节点]) ll son[100005]; //表示删去节点x后剩下的连通分量中最大子树节点个数。其中一部分在原来i其为根的子树 //son[i]=max(son[i] , siz[i的儿子节点]) ll r1,r2; ll n; //每个图有多少个点 void dfs(ll u,ll fa) { siz[u]=1; son[u]=0; for(ll i=0;i<g[u].size();i++) { ll v=g[u][i]; if(v==fa) continue; dfs(v,u); siz[u]+=siz[v]; son[u]=max(son[u],siz[v]); } son[u]=max(son[u],n-siz[u]); if((son[u]<<1)<=n) { r2=r1; r1=u; } } int main() { ll T; cin >> T; while(T--) { cin >> n; for(ll i=0;i<=n+10;i++) //初始化 { g[i].clear(); siz[i]=0; son[i]=0; } for(ll i=1;i<n;i++) //一共n-1条边 { ll x,y; cin >> x >> y; g[x].push_back(y); //点x跟点y链接 g[y].push_back(x); //点y跟点x链接 } r1=r2=0; //r1记录的是 dfs(1,0); if(r2==0) //如果只有一个重心,则直接删除跟重心相连的一条边,并且重新加回去就可以了(r1是重心的坐标) { ll r3 = g[r1][0]; //r3是跟r1相连的另一个点的坐标 cout << r1 << " " << r3 << endl; cout << r1 << " " << r3 << endl; } else //如果有两个重心 { ll r3=r1; for(ll i=0;i<g[r2].size();i++) { r3 = g[r2][i]; if(r3!=r1) break; } cout << r3 << " " << r2 << endl; cout << r3 << " " << r1 << endl; } } return 0; }