Garland

可能就我写的比较麻烦...emmm菜的真实.我写了两个dfs,因为我不想写lca...acm带板子还是好..写完看了评论区,都比我短.
思路就是dfs1找到第一个sum/3,dfs2找到第二个sum/3即可.

//i<->ai ti a[i]=0的i为根节点
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int w[N];//i上面连着的点的权值是多少.
vector<int>v[N];
vector<int>ans;
int sum[N];//记录下i为根的子树的权值.
map<int,int>mp[N];
int cnt,num,root,mk;
int dfs1(int u,int fa)//找到第一个cnt/3的点.
{
    sum[u]+=w[u];
    if(ans.size())    return 0;
    for(int i=0;i<v[u].size();i++)
    {
        int son=v[u][i];
        if(fa==son)    continue;
        sum[u]+=dfs1(son,u);
    }
    if(ans.size()==0&&sum[u]==cnt&&u!=0)
    {
        ans.push_back(mp[u][fa]);
        root=fa;
        mk=u;
    }
    return sum[u];
}

int dfs2(int u,int fa)
{
    sum[u]+=w[u];
    if(ans.size()>1)    return 0;
    for(int i=0;i<v[u].size();i++)
    {
        int son=v[u][i];
        if(fa==son)    continue;
        sum[u]+=dfs2(son,u);
    }
    if(ans.size()==1&&sum[u]==cnt&&u!=0&&mp[u][fa]!=ans[0])
    {
        ans.push_back(mp[u][fa]);
    }
    return sum[u];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d%d",&x,&w[i]);
        cnt+=w[i];
        v[x].push_back(i);v[i].push_back(x);
        mp[x][i]=i;mp[i][x]=i;

    }
    if(cnt%3)    {  puts("-1"); return 0;  }
    else            cnt/=3;
    dfs1(0,-1);
   // cout<<sum[0]<<endl;
   // cout<<root<<' '<<mk<<endl;
    memset(sum,0,sizeof sum);
    dfs2(root,mk);
    (ans.size()!=2)?puts("-1"):printf("%d %d\n",ans[0],ans[1]);
    return 0;
}