Garland

动笔之前多想想可以节约很多时间

想象一下删掉某条边会会发生什么

就是把以为根的子树砍掉,此时满足子树内的权值是树的三分之一

但是砍掉时候,的祖先们就不能利用这些权值了,所以设置为0

就这样一遍回溯就可以解决

亏我还想了那么久......彩笔

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int f[maxn],root,a[maxn],su,c[maxn];
int ans,q,w;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){
    d[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to;
        if( v==fa )    continue;
        dfs1(v,u);
        f[u]+=f[v];
    }
    if( f[u]==su )
    {
        ans++; f[u]=0;
        if( q&&!w )    w=u;
        else if( !q&&!w )    q=u;
    }
}
int main()
{
    int n,m,sumn=0;
    cin >> n ;
    for(int i=1;i<=n;i++)
    {
        int x; scanf("%d%d",&x,&f[i]);
        sumn+=f[i];
        if( x==0 )    root=i;
        else add(x,i), add(i,x);
    }
    if( sumn%3!=0 )    cout << -1;
    else
    {
        su=sumn/3;
        dfs1(root,0);
        if( ans>=3)    cout << q << " " << w;
        else    cout << -1;
    }
}