【题解】改造森林

题意

给你一棵有个节点的树，你可以在树上删掉两条边，使得树变为三棵子树，且要求三棵子树的节点个数要相同。问能否实现，能输出,否则输出。

题解

首先先判断整颗树的节点个数能否被三整除，若不行肯定无法划分为三个节点树相同的子树。然后我们对这棵树进行，来计算出每个节点作为根时该子树的节点个数，记为。再遍历数组找是否有子树的节点数量为，若有将该子树删除，在该子树上的节点的赋值为，再从向上寻找祖先，将。然后我们再遍历一次数组查看是否还有子树的大小为，有则说明可以实现划分输出。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>E[N];
int fa[N];
int sum[N];
bool vis[N];
int n;
void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<E[u].size();i++)
    {
        int v=E[u][i];
        if(!vis[v])
        {
            fa[v]=u;
            dfs(v);
            sum[u]+=sum[v];
        }
    }
}
void cut(int u)
{
    for(int i=0;i<E[u].size();i++)
    {
        int v=E[u][i];
        if(v==fa[u])
        {
            sum[v]-=n/3;
            cut(v);
        }
    }
}
void sub(int u)
{
    sum[u]=0;
    for(int i=0;i<E[u].size();i++)
    {
        int v=E[u][i];
        if(v!=fa[u])
        {
            sub(v);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) E[i].clear(),sum[i]=1;
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            E[u].push_back(v);
            E[v].push_back(u);
        }
        if(n%3!=0)
        {
            printf("NO\n");
            continue;
        }
        dfs(1);
        memset(vis,0,sizeof(vis));
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(sum[i]==(n/3))
            {
                cut(i);
                sub(i);
                flag++;
                break;
            }
        }
        if(flag==0)
        {
            printf("NO\n");
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            if(sum[i]==(n/3))
            {
                flag++;
                break;
            }
        }
        if(flag==2)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}