花了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-7; const int N=1000000+10,maxn=300000+10,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=0;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=0;i<v[u].size();i++) if(v[u][i]!=f) { if(t[v[u][i]]==2*t[s]/3)dfs1(v[u][i],u,v[u][i],one); else if(t[v[u][i]]==t[s]/3) { ans.insert(v[u][i]); ma[one]=1; if(two!=0) { cout<<two<<" "<<v[u][i]<<endl; exit(0); } 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(0); int n; cin>>n; for(int i=1;i<=n;i++) { int a; cin>>a>>t[i]; if(a==0) { s=i; continue; } v[a].push_back(i); v[i].push_back(a); } dfs(s,-1); // cout<<t[3]<<endl; if(t[s]%3!=0) { cout<<-1<<endl; return 0; } dfs1(s,-1,0,0); // for(auto u:ans)cout<<u<<endl; v[0].clear(); for(auto u:ans) if(!ma[u]) v[0].push_back(u); if(v[0].size()>=2)cout<<v[0][0]<<" "<<v[0][1]<<endl; else cout<<-1<<endl; return 0; } /******************** 5 0 2 1 2 2 -1 3 -1 4 1 ********************/