Garland

题意

你有一颗个节点的树，每个节点有一个点权，现在要求将这一棵树拆为三棵子树，子树的权值之和相等。

思路

由于点权之和确定，那么每棵子树的权值之和就一定。那么我们只需要搜索，当当前记录的权值之和为所有点权值的三分之一时，记录下答案和答案个数。当答案个数小于时，输出

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,cnt,rt,py,sum;
int head[N],a[N];
struct node
{
    int to,nxt;
}e[N<<1];
vector<int > ans;

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

int dfs(int fa,int now)
{
    int tot=a[now];
    for(int i=head[now];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==fa)    continue ;
        tot+=dfs(now,to);
    }
    if(tot*3==sum)
    {
        ans.push_back(now);
        tot=0;
    }
    if(ans.size()==3)
    {
        for(int i=0;i<ans.size()-1;i++) 
            printf("%d ",ans[i]);
        exit(0);
    }
     return tot;
}


int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int u;
        u=read();a[i]=read();
        sum+=a[i];
        add(u,i);add(i,u);
        if(!u)    rt=i;
    }
    dfs(0,rt);
    printf("-1");
    return 0;
}