分析

我们对于每个子树的答案是可以预先知道的 ，那么如果 那么一定无解。之后我们可以直接遍历整个树得到 的节点。那么当这样的节点个数超过 的时候，这个树就是合法的，输出两个非树根的节点就可以了。那么总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return f?-x:x;
}
const int N = 1e6 + 10;
vector<int> G[N],A;
int n,val[N],sum[N],Ans,rt;
void dfs(int x,int fa){
    sum[x]=val[x];for(auto y:G[x]){
        if(y==fa)continue;
        dfs(y,x);sum[x]+=sum[y];
    }if(sum[x]*3==Ans)A.push_back(x),sum[x]=0;
}
int main() {
    n=read();for(int i=1,a;i<=n;i++){
        a=read();val[i]=read();
        if(!a) rt=i;else {
            G[a].push_back(i);G[i].push_back(a);
        }
        Ans+=val[i];
    }
    if(Ans%3){cout<<"-1"<<endl;return 0;}
    dfs(rt,0);if(A.size()<=2) {cout<<"-1"<<endl;return 0;}
    cout<<A[0]<<" "<<A[1]<<endl;return 0;
}