可能就我写的比较麻烦...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; }