考察:树形dp
树的重心变种题
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。(不止一个)
模板题 树的重心
思路:
把树的某个点删去后,剩余部分是不包含父节点的子节点连通块.已经删去点的父节点连通块.通过dfs可以求出子节点连通块,父节点连通块是结点总数-父节点-子节点和
本题求的是破坏某点后,使得连通块之间的最大距离最小.实际上是树的重心
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 const int N = 10010,INF = 0x3f3f3f3f; 8 int h[N],idx,ans = INF,n; 9 vector<int> v; 10 struct Road{ 11 int to,ne; 12 }road[N<<1]; 13 void add(int a,int b) 14 { 15 road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 16 } 17 int dfs(int u,int fa) 18 { 19 int res = 0,sum = 1; 20 for(int i=h[u];i!=-1;i=road[i].ne) 21 { 22 int v = road[i].to; 23 if(v==fa) continue; 24 int s = dfs(v,u); 25 res = max(s,res); 26 sum+=s; 27 } 28 int tmp = max(n-sum,res); 29 if(tmp<ans) ans = tmp,v.clear(),v.push_back(u); 30 else if(tmp==ans) v.push_back(u); 31 return sum; 32 } 33 int main() 34 { 35 memset(h,-1,sizeof h); 36 scanf("%d",&n); 37 for(int i=1;i<n;i++) 38 { 39 int x,y; 40 scanf("%d%d",&x,&y); 41 add(x,y); add(y,x); 42 } 43 dfs(1,-1); 44 sort(v.begin(),v.end()); 45 if(v.empty()) puts("NONE"); 46 else 47 for(int i=0;i<v.size();i++) printf("%d\n",v[i]); 48 return 0; 49 }
原文：https://www.cnblogs.com/newblg/p/14408626.html