主要是留个板子
因为我似乎不会证明
树直径
丛树的任一点开始找一个离该节点最远的点，该点必为树直径的一端点，再从该点出发找最远点即为树直径
方法：dfs 时间O(2n)
树重心
以某个节点为树根，最大子树最小的节点
方法是树dp 时间O(n)
要注意的点都在代码注释里
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=0x3f3f3f; const int N=5e5+7; int dp[N];///存该节点不走父边的所有节点和 vector<int>son[N];///vector邻接表存树 int mi;///最大子树最小值 int n,m; int a[N];///以下标为节点的树的最大子树节点数 void dfs(int x,int fa) { dp[x]=1; a[x]=0; for(int i=0;i<son[x].size();i++) { if(son[x][i]==fa) continue; dfs(son[x][i],x); dp[x]+=dp[son[x][i]]; a[x]=max(a[x],dp[son[x][i]]); } a[x]=max(a[x],n-dp[x]); if(a[x]<mi) mi=a[x]; } int main() { ios::sync_with_stdio(false); cin>>n; m=n-1; mi=n; while(m--) { int a1,a2; cin>>a1>>a2; son[a1].push_back(a2); son[a2].push_back(a1); } dfs(1,0); for(int i=1;i<=n;i++) if(a[i]==mi) cout<<i<<' ';cout<<endl; }
