CF1829F Forever Winter 题解
cjh20090318
·
·
题解
大家好，我是 CQ-C2024 蒟蒻 CJH。
题意
一个雪花图可以通过两个大于 1 的整数 x 和 y 生成，具体步骤如下：
- 从一个中心点开始。
- 将 x 个新的顶点连接到该中心点。
- 将 y 个新的顶点分别连接到上述 x 个新顶点中的每个顶点。
给你一个雪花图，请找出它的 x 和 y。
分析
观察题面图片可以发现，一个雪花图一定是一棵无根树。
也就是说，我们求 x 只需要求出树的重心即可，x 的值即为重心的出度。
## 注意事项
**本题有多组数据。**
所以一定要把存图的 `vector` 清空！
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
vector<int> G[202];
int rt,s[202],dp[202];。
bool vis[202];
void dfs(int x,int fa,const int sum){//求树的重心。
s[x]=1,dp[x]=0;
for(int v:G[x])
if(v!=fa && !vis[v]){
dfs(v,x,sum);
s[x]+=s[v];//统计子树大小。
dp[x]=max(dp[x],s[v]);
}
dp[x]=max(dp[x],sum-s[x]);
if(dp[x]<dp[rt]) rt=x;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) G[i].clear();//多测要清空邻接表！
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
rt=0,dp[0]=202;memset(vis,0,sizeof vis);//清空访问数组。
dfs(1,0,n);
printf("%d %d\n",(int)G[rt].size(),(int)G[G[rt][0]].size()-1);//重心的出度和重心任意一个子节点出度减去一。
}
int main(){
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}
```