Codeforces C. Link Cut Centroids(树的重心)
作者:
我不会取名字啊啊
,
2022-05-12 20:15:24
,
所有人可见
,
阅读 199
emmm...不会...
树的重心,结论,构造题...
分析一下:
树的重心:删掉这个节点,形成的最大连通分量的最小。
找树的重心就随便dp一下就行(板子),主要是性质
性质:
1. 删除重心后所得的所有子树,节点数不超过原树的1/2;
2. 树中所有节点到重心的距离之和最小,如果有两个重心,那么他们距离之和相等;
3. 两个树通过一条边合并,新的重心在原树两个重心的路径上;
4. 树删除或添加一个叶子节点,重心最多只移动一条边;
5. 一棵树最多只有两个重心!!!
6. 两个重心相邻!!!
所以题目就转换成:如何构造,把有两个重心的树变成只有一个重心的树?
构造:把一个重心的子树拿到另一个重心上;
vector<int> g[maxn];
int sz[maxn];
int son[maxn];
int n;
void dfs(int u,int fa)
{
sz[u] = 1;
son[u] = 0;
for(auto v : g[u])
{
if(v == fa) continue;
dfs(v,u);
sz[u] += sz[v];
son[u] = max(son[u],sz[v]);
}
son[u] = max(son[u],n-sz[u]);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,-1);
int mini = inf;
for(int i=1;i<=n;i++) mini = min(mini,son[i]);
int v1,v2;
v1 = v2 = 0;
for(int i=1;i<=n;i++)
if(son[i] == mini)
{
if(v1 == 0) v1 = i;
else v2 = i;
}
if(v2 == 0)
{
for(auto v : g[v1])
{
cout<<v1<<' '<<v<<endl;
cout<<v1<<' '<<v<<endl;
break;
}
}
else
{
for(auto v : g[v1])
{
if(v == v2) continue;
cout<<v<<' '<<v1<<endl;
cout<<v<<' '<<v2<<endl;
break;
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}