ZOJ 3684 Destroy 树的中心

中心节点就是树的中心，2遍dfs求到树的直径，而中心一定在直径上，顺着直径找到中心就够了。

然后可以一遍树形DP找到最小值或者二分+判断是否访问到叶子节点。

#include 
  
   
#include
   
     #include
    
      #include
     
       using namespace std; struct node { int next; int power; int length; }t; vector
      
        tree[10005]; int st,ed,maxs,n; void dfs1(int now,int fa,int sum) { if(sum>maxs) { maxs=sum; st=now; } for(int i=0;i
       
        maxs) { maxs=sum; ed=now; } for(int i=0;i
        
         lim) { if(!cal(to,now,lim)) return false; } } return true; } int main() { int maxx; int a,b,c,d; while(~scanf("%d",&n)) { maxx=0; for(int i=1;i<=n;i++) tree[i].clear(); for(int i=1;i
         
          >1; if(cal(zx,-1,mid)) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); } return 0; } /* 7 1 2 8 2 1 3 2 2 3 6 4 0 2 4 3 0 2 5 10 0 5 7 12 0 */