【CodeForces 767C】Garland （樹形DP）

題目描述：

garland

算法：

樹形DP（思路較簡單，但有難想到的細節）

題目大意：

給你一個 n(3≤n≤106) 個點的樹，每個點 i 都有點權 ti，讓你在樹中去除兩條邊使得三部分的點權和相等，每一部分至少有一個點。

做法：

先求出所有點的點權和 all ，如果 all 不能整出3，則無解。因為删去一條邊後，一個子樹就沒了，是以求出每一個子樹 i 的點權和 sizi，如果 sizi=all/3 ，則删去連 i <script id="MathJax-Element-505" type="math/tex">i</script> 的那條邊。

但有一些細節：

1. 即使 all 能整除 3，也不一定有兩個點滿足條件。

如樣例：5 0 4 1 1 1 2 2 1 2 1

2. 即使有兩個點滿足，如果有一個點是根，也無解。

如樣例：4 0 1 1 -1 2 1 3 -1

我是以 WA 了兩次。。。我太不認真了。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N=;
int n;
vector <int> V[N];

int beg, all, cnt;
int p[N], siz[N], ans[N];

void dfs(int u){
    siz[u] = p[u];
    for(int i=, sz=V[u].size(), v; i<sz; ++i){
        v = V[u][i];
        dfs(v);
        siz[u] += siz[v];
    }
    if(siz[u]==all){ ans[++cnt]=u; siz[u]=; }      // 記錄答案  
}

int main(){
    scanf("%d",&n);
    for(int i=, x; i<=n; ++i){
        scanf("%d%d", &x, &p[i]); all += p[i];
        if(x) V[x].push_back(i);
        else beg=i;         // 找到起點  
    }
    if(all%){ puts("-1"); return ; }              // all 必須整除 3 
    all /= ;
    dfs(beg);
    if(cnt< || ans[]==beg) puts("-1");            // 細節啦  
    else printf("%d %d\n",ans[], ans[]);
    while();
}