题意:把一颗树分成3部分,使得每一部分的点权和相等
很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就sz重置成0.
//Codeforces Round 767C
//树形结构,算子树总和
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+6;
struct N{
int v,nxt,w;
}node[maxn<<2];
int sum,num,cnt,head[maxn<<2];
int size[maxn],w[maxn];
int ans[3];
void add(int u,int v)
{
++cnt;
node[cnt].v = v;
node[cnt].nxt= head[u];
head[u] = cnt;
}
void dfs(int u,int fa){
size[u] = w[u];
for(int v,i=head[u];i;i=node[i].nxt){
v = node[i].v;
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v];
}
if(size[u]==sum)ans[++num]=u,size[u] = 0;
}
int main()
{
int n,v,root;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&v,&w[i]);
sum+=w[i];
if(v==0){
root = i; continue;
}
add(v,i); add(i,v);
}
if(sum%3!=0){
printf("-1\n");
}else{
sum/=3;
dfs(root,0);
if(num<=2){printf("-1\n");return 0;}
printf("%d %d\n",ans[1],ans[2]);
}
return 0;
}