题目链接U392706 【模板】树的中心 - 洛谷https://www.luogu.com.cn/problem/U392706题面# U392706 【模板】树的中心## 题目背景树的中心定义为一个节点作为整棵树的根节点时深度最大的节点的深度最小则该节点是树的中心。注意树的中心不一定唯一。## 题目描述给定一棵 $n$ 个节点的树求树的所有中心。## 输入格式第一行一个整数 $n$。接下来 $n-1$ 行每行三个整数$x,y,z$表示存在一条边 $(x,y)$边权为 $z$。## 输出格式若干行每行一个整数表示所有树的中心的节点编号从小到大排序。## 输入输出样例 #1### 输入 #1101 2 31 3 42 4 52 5 75 6 65 7 56 9 96 10 17 8 2### 输出 #15## 输入输出样例 #2### 输入 #251 2 41 3 02 4 01 5 4### 输出 #213## 说明/提示$1\le n,x,y\le 10^6,z\le 10^9$。正文这个代码只要你实现一件事在一棵树里找到「树的中心」并按从小到大输出。而tree的中心结点有三个特点feature到直径两端点的最大距离最小的点最多只有1 个直径为偶数 或 2 个直径为奇数一定在直径上然后就木有了…………所以我们的代码需要围绕这个思路来写。思路First你需要输入一个树存在一个Vector里面。Second你需要使用两次DFS找到直径的两个端点这是在求树的直径。Third你需要在直径上找中心节点。直径是一条路径d1 —— …… —— d2对直径上每一个点计算两个值到 d1 的距离到 d2 的距离取较大的那个然后找到让这个最大值最小的点。这就是树的中心Fourth收集所有符合条件的中心排序输出。思路都讲好了肯定没有问题了吧。AC代码#includebits/stdc.h using namespace std; vectorpairint,int g[1000005]; long long de[1000005]; int father[1000005]; int n,tmp; void dfs(int u,int fa,long long d){ de[u]d; father[u]fa; if(de[u]de[tmp])tmpu; for(int i0;ig[u].size();i){ int vg[u][i].first; int wg[u][i].second; if(vfa)continue; dfs(v,u,dw); } } int main(){ cinn; for(int i1;in;i){ int u,v,w; cinuvw; g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs(1,0,0); int d1tmp; dfs(d1,0,0); int d2tmp; long long minx1e18; tmpd2; while(1){ long long dismax(de[d2]-de[tmp],de[tmp]); if(disminx)minxdis; if(tmpd1)break; tmpfather[tmp]; } int a[1000005]; int cnt1; tmpd2; while(1){ long long dismax(de[d2]-de[tmp],de[tmp]); if(minxdis)a[cnt]tmp; if(tmpd1)break; tmpfather[tmp]; } cnt--; sort(a1,acnt1); for(int i1;icnt;i){ couta[i]endl; } return 0; }AC记录记录详情 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/record/273621007Thanks for watching