树的中心问题是指：当给出 n 个结点与 n-1 条边后，要选定一个点作为整棵树的根结点，使得从该点到每个子结点的最长路径最短。
树的中心问题主要有两种方法：BFS/DFS 进行搜索、树形 DP 进行状态转移
例题：
U392706 【模板】树的中心
题目背景
树的中心定义为：一个节点作为整棵树的根节点时，深度最大的节点的深度最小，则该节点是树的中心。
注意，树的中心不一定唯一。
题目描述
给定一棵 n 个节点的树，求树的所有中心。
输入格式
第一行一个整数 n。
接下来 n−1 行每行三个整数：x,y,z，表示存在一条边 (x,y)，边权为 z。
输出格式
若干行，每行一个整数，表示所有树的中心的节点编号，从小到大排序。
思路
首先的中心一定位于树的直径上，且树的中心就是树的直径的中点，所以就需要找到直径之后再遍历一遍，找到其中靠中间的一个或两个节节点
代码
#include<bits/stdc++.h>0 using namespace std; long long n , x , y , z , cnt , a[1000005] , depth[10000005] , tmp , father[10000005]; vector <pair<long long , long long> > g[100005]; void dfs(int u , int fa , int d){ depth[u] = d; father[u] = fa; if(depth[u] > depth[tmp]){ tmp = u; } for(int i = 0;i < g[u].size();i++){ int v = g[u][i].first; int w = g[u][i].second; if(v == fa){ continue; } dfs(v , u , d + w); } } long long vis[100005]; void dfs2(int u){ if(vis[u]){ return; } a[++cnt] = u; vis[u] = true; for(int i = 0;i < g[u].size();i++){ int v = g[u][i].first; int w = g[u][i].second; if(w == 0 && !vis[u]){ dfs2(v); } } } int main(){ scanf("%d" , &n); for(int i = 1;i < n;i++){ scanf("%d%d%d" , &x , &y , &z); g[x].push_back({y , z}); g[y].push_back({x , z}); } dfs(1 , 0 , 0); int d1 = tmp; dfs(tmp , 0 , 0); int d2 = tmp; int minx = 0x3f3f3f3f; tmp = d2; while(1){ int cont = max(depth[d2] - depth[tmp] , depth[tmp]); minx = min(minx , cont); if(tmp == d1){ break; } tmp = father[tmp]; } tmp = d2; while(1){ int cont = max(depth[d2] - depth[tmp] , depth[tmp]); if(cont == minx){ a[++cnt] = tmp; } if(tmp == d1){ break; } tmp = father[tmp]; } sort(a + 1 , a + 1 + cnt); for(int i = 1;i <= cnt;i++){ cout << a[i] <<endl; } return 0; }
