【题目链接】:http://codeforces.com/contest/767/problem/C

【题意】



一棵树;

树上的每个节点都有一个权值;

让你把一棵树切掉两条边;

然后把这棵树分成了3个部分;

要求这3个部分,每个部分的权值和相同;

即sum1=sum2=sum3

【题解】



树形DP;

一开始累加所有节点的权值和sum;

如果不是3的倍数则直接输出无解;

用cnt[x]记录x节点下方的子树和(权值和);

假设dfs到了第x个节点

考虑两种情况;

①

有两个节点y,z;

且sum/3==cnt[y]==cnt[z]

且y和z分别在x的两个儿子节点所在的子树中;

输出y和z就好

②

2/3*sum==cnt[x];

然后x的子树里面有另外一个节点y

满足1/3*sum==cnt[y];

输出x和z就好

这里注意x不能为根节点!

定义个数组往上传这个子树里面有没有1/3sum和2/3sum就好;



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

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

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 1e6+1000;

int n,sum=0,goal;

int fa,w[N],root,cnt[N],haved1[N],haved2[N];

vector <int> G[N];

void dfs(int x)

{

    cnt[x] = w[x];

    int num = 0,a[5];

    for (int y : G[x])

    {

        dfs(y);

        if (haved1[y])

        {

            haved1[x] = haved1[y];

            a[++num] = haved1[y];

            if (num > 1)

            {

                printf("%d %d\n", a[1], a[2]);

                exit(0);

            }

        }

        if (haved2[y]) haved2[x] = haved2[y];

        cnt[x] += cnt[y];

    }

    if (cnt[x] == goal) haved1[x] = x;

    if (cnt[x] == 2 * goal) haved2[x] = x;

    if (x!=root && 2*goal==cnt[x])

    {

        for (int y : G[x])

        {

            if (haved1[y])

            {

                printf("%d %d\n", haved1[y], x);

                exit(0);

            }

        }

    }

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(n);

    rep1(i, 1, n)

    {

        rei(fa), rei(w[i]);

        if (fa == 0)

            root = i;

        G[fa].ps(i);

        sum += w[i];

    }

    if (sum % 3) return puts("-1"), 0;

    goal = sum / 3;

    dfs(root);

    puts("-1");

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}