1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; vector <int> a[maxn]; //邻接表,记录点与边的关系 int deep[maxn]; //记录每个节点的深度 int cnt[maxn]; //统计树每层的节点数量 int maxDeep=1,c1=0,c2=0;//树的最大深度,奇数层节点总数,偶数层节点总数 int n; void dfs(int v, int f){ deep[v]=deep[f]+1; //记录当前节点在第几层 maxDeep=max(maxDeep,deep[v]); //计算树的最大深度 cnt[deep[v]]++; //当前节点所在层的节点总数+1 //遍历当前节点的邻居 for(int i=0;i<int(a[v].size());i++){ int nv=a[v][i]; //邻居 if(nv==f) continue; //避免无限递归 dfs(nv,v); } } int main(){ int u,v; cin >> n; //用邻接表记录所有节点之间的邻接关系 for(int i=1;i<n;i++){ cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } //深搜遍历整棵树,记录每个节点所在层,以及统计树的每层的节点总数 dfs(1,0); // for(int i=1;i<=maxDeep;i++){ if(i&1) c1+=cnt[i]; //奇数层节点数量 else c2+=cnt[i]; //偶数层节点数量 } // for(int i=1;i<=n;i++){ if(deep[i]&1) cout << c1 << " "; else cout << c2 << " "; } // return 0; }
- 1
信息
- ID
- 1229
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 7
- 已通过
- 2
- 上传者