题目链接

http://codeforces.com/problemset/problem/767/C

题目大意

给你一颗树，每个点上有值，现在需要你删除两条边使得生成的三棵树每棵树上所有点的权值和一样

题目分析

这题只需要一遍DFS就可以了，记录子树上所有的权值和，只要某一棵子树的值达到总和的三分之一就说明这颗子树可以分离，于是可以将这颗子树的权值和视为零，记录下这条边，最后看如果得到的边少于两条便是没有解，如果有两条边只要输出这两条就可以了

最后注意读入量很大用cin可能会超时

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

struct ex {
    int y;
    int next;
};

ex e[2000005];
int eb[2000005];
int ec = 0;
int n;

int tt[2000005];
int sum = 0;
int root;

int et[5];
int etc = 0;

int addedge(int x, int y){
    ec++;
    
    e[ec].y = y;
    e[ec].next = eb[x];
    eb[x] = ec;
    
    return 0;
}

int dfs(int x){
    int y;
    int enow;
    
    enow = eb[x];
    
    while(enow){
        
        y = e[enow].y;
        dfs(y);
        
        if(tt[y] == sum){
            etc++;
            et[etc] = enow;
            tt[y] = 0;
        }
        
        tt[x] += tt[y]; 
        
        enow = e[enow].next;
    }
    
    return 0;
}

int main(){
    int i, j;
    int x, y, z;
    
    scanf("%d", &n);
    
    for(i=1;i<=n;i++){
        scanf("%d", &x);
        scanf("%d", &tt[i]);
        sum += tt[i];
        addedge(x, i);
    }
    
    root = e[eb[0]].y;
    
    if(sum % 3){
        printf("-1n");
        return 0;
    }
    
    sum /= 3;
    
    dfs(root);
    
    if(etc >= 2){
        printf("%d %dn", e[et[1]].y, e[et[2]].y);
    }else{
        printf("-1n");
    }
    
    return 0;
}