https://codeforces.com/contest/1406/problem/C
做這個題前提是要知道樹的重心，百度拉了一下，
參考一下：https://blog.csdn.net/weixin_43810158/article/details/88391828
樹的重心定義為樹的某個節點，當去掉該節點后，樹的各個連通分量中，節點數最多的連通分量其節點數達到最小值，樹可能存在多個重心，如下圖,當去掉點1后，樹將分成兩個連通塊：（2,4,5），（3,6,7），則最大的連通塊包含節點個數為3，若去掉點2，則樹將分成3個部分，（4），（5），（1,3,6,7）最大的連通塊包含4個節點；第一種方法可以得到更小的最大聯通分量，可以發現，其他方案不可能得到比3更小的值了，所以，點1是樹的重心，
性質：
1.洗掉重心后所得的所有子樹，節點數不超過原樹的1/2，一棵樹最多有兩個重心；
2.樹中所有節點到重心的距離之和最小，如果有兩個重心，那么他們距離之和相等；
3.兩個樹通過一條邊合并，新的重心在原樹兩個重心的路徑上；
4.樹洗掉或添加一個葉子節點，重心最多只移動一條邊；
5.一棵樹最多有兩個重心，且相鄰，
思路：如果找到只有一個重心，那么直接刪一個重心的直連邊然后加回去就好了，
如果找到兩個重心，那么在其中一個重心上找到一個直連點不是另一個重心，洗掉連另外一個就好了，
如何求樹的重心？，
先任選一個結點作為根節點，把無根樹變成有根樹，然后設siz[i]表示以i為根節點的子樹節點個數，轉移為siz[i]=∑（siz[i的兒子節點] );
設son[i]表示刪去節點x后剩下的連通分量中最大子樹節點個數，其中一部分在原來i其為根的子樹，son[i]=max(son[i],siz[i的兒子節點]);
另外一部分在i的“上方”子樹有n-siz[i]個， son[i]=max(son[i],n-siz[i]);
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
vector<LL>g[maxn];
LL siz[maxn],son[maxn];
LL r1,r2,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(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
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++){
LL x,y;cin>>x>>y;
g[x].push_back(y);g[y].push_back(x);
}
r1=r2=0;
dfs(1,0);
if(!r2){
LL r3=g[r1][0];
cout<<r1<<" "<<r3<<endl;
cout<<r1<<" "<<r3<<endl;
}
else{
LL r3=r1;
// debug(r1);debug(r2);
for(LL i=0;i<g[r2].size();i++){
r3=g[r2][i];
// debug(r3);
if(r3!=r1) break;
}
cout<<r3<<" "<<r2<<endl;
cout<<r3<<" "<<r1<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/52658.html
標籤：其他
上一篇：用c++圖形庫撰寫的雙人打氣球