CodeForces - 767C

花了6个小时，终于成功ac。。。。。。

两边dfs，第一遍求子树和，第二遍判断有没有2*t【s】/3和t【s】/3，因为要求的节点可能是在同一条线上，同时要有2*t【s】/3和t【s】/3的情况，且2*t【s】/3距根节点更近

还要注意的是如果同一条线上有两个t【s】/3的点是行不通的，必须要在两个不同分支上

结果跑了1996ms，险过=-=

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

ll t[N];

int s;

vector<int>v[N];

set<int>ans;

map<int,int>ma;

void dfs(int u,int f)

{

    for(int i=;i<v[u].size();i++)

        if(v[u][i]!=f)

        {

           dfs(v[u][i],u);

           t[u]+=t[v[u][i]];

        }

}

void dfs1(int u,int f,int two,int one)

{

   // cout<<u<<" "<<f<<" "<<two<<" "<<one<<endl;

    for(int i=;i<v[u].size();i++)

        if(v[u][i]!=f)

        {

            if(t[v[u][i]]==*t[s]/)dfs1(v[u][i],u,v[u][i],one);

            else if(t[v[u][i]]==t[s]/)

            {

                ans.insert(v[u][i]);

                ma[one]=;

                if(two!=)

                {

                    cout<<two<<" "<<v[u][i]<<endl;

                    exit();

                }

                else dfs1(v[u][i],u,two,v[u][i]);

            }

            else dfs1(v[u][i],u,two,one);

        }

   // if(v[u].size()==1&&one!=0)ans.insert(one);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n;

    cin>>n;

    for(int i=;i<=n;i++)

    {

        int a;

        cin>>a>>t[i];

        if(a==)

        {

            s=i;

            continue;

        }

        v[a].push_back(i);

        v[i].push_back(a);

    }

    dfs(s,-);

   // cout<<t[3]<<endl;

    if(t[s]%!=)

    {

        cout<<-<<endl;

        return ;

    }

    dfs1(s,-,,);

  //  for(auto u:ans)cout<<u<<endl;

    v[].clear();

    for(auto u:ans)

        if(!ma[u])

           v[].push_back(u);

    if(v[].size()>=)cout<<v[][]<<" "<<v[][]<<endl;

    else cout<<-<<endl;

    return ;

}

/********************

5

0 2

1 2

2 -1

3 -1

4 1

********************/