本文共 918 字，大约阅读时间需要 3 分钟。

1、

2、题目大意：

一棵树有n个点，每个点都有一个平衡值，就是该点的子树中结点数最大值，现在要删除这样一个点，他的平衡值最小，本题只有一种方式，不用考虑是否有重复值，只需要输出最小的那个点及他的平衡值即可

dp[i]表示i点的平衡值

dp[i]=max(max(cnt[v]),n-cnt[u])

3、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 20005#define INF 20005int v[N*2],next[N*2],head[N*2];int tot;int cnt[N];int ans,res,n;int dp[N];void add_edge(int a,int b){    v[tot]=b;    next[tot]=head[a];    head[a]=tot++;}void dfs(int u,int fa){    cnt[u]=1;    for(int i=head[u];i!=-1;i=next[i])    {        int vv=v[i];        if(vv!=fa)        {            dfs(vv,u);            cnt[u]+=cnt[vv];            ans=max(ans,cnt[vv]);        }    }    dp[u]=max(ans,n-cnt[u]);    res=min(dp[u],res);}int main(){    int t,a,b;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        tot=0;        memset(head,-1,sizeof(head));        memset(cnt,0,sizeof(cnt));        memset(dp,0,sizeof(dp));        for(int i=1;i
     
    
   

转载地址：http://hrddi.baihongyu.com/