codeforce 767C Garland (樹形dp)

題意：給你一棵樹，每個節點都有一個權值，之後你可以删除兩條邊把他變成3顆子樹現在使得他的三顆的權值相等。

思路：顯然他們的點權都是3的倍數才會得到3顆權值相等的樹，那麼我們就樹形dp，自下而上的求出以某個點為根的子樹的權值，如果他的權值等于sum/3 那麼就讓這顆子樹的權值為0，接着dfs就好了

代碼：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
vector<int>V[maxn];
vector<int>ANS;
int Size[maxn] , cur , W[maxn];
void dfs(int u ,int fa)
{
    Size[u] = W[u];
    for(int i = 0 ; i < V[u].size() ; i ++)
    {
        int v = V[u][i];
        if(v == fa) continue;
        dfs(v,u);
        Size[u] += Size[v];
    }
    if(Size[u] == cur) {ANS.push_back(u),Size[u] = 0;}
}
int main()
{
    int n;
    scanf("%d",&n);
    int pos , val , root , sum = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d%d",&pos, &val);
        if(pos == 0) {root = i;}
        V[i].emplace_back(pos);
        V[pos].emplace_back(i);
        W[i] = val;
        sum += val;
    }
    if(sum%3) {puts("-1");return 0;}
    cur = sum/3;
    dfs(root,0);
    if(ANS.size() <= 2) {puts("-1"); return 0;}
    cout<<ANS[0]<<" "<<ANS[1]<<endl;

}
/*
4
0 1
1 -1
2 1
3 -1
*/