大體題意：

給你一顆樹，要求切掉兩個邊，使得剩下的三個子樹權值相同，問切哪兩個邊？ 沒有輸出-1

思路：

因為第一次刪除肯定是刪除一個完整子樹。

所以直接統計出每個點包含的完整子樹的權值之和， 發現一個點的權值之和等于sum/3 的話，就把它切掉，直到切掉兩個為止。

注意：

切掉之后點的權值之和會發生改變。

其次 根節點不能被切。

#include <bits/stdc++.h>#define mr make_pair#define ps push_back#define fi first#define se second#define Siz(x) (int)x.size()using namespace std;typedef long long LL;typedef unsigned long long ULL;const double eps = 1e-10;const int inf = 0x3f3f3f3f;const double pi = acos(-1.0);const int maxn = 1e6 + 10;vector<int>g[maxn];int sum = 0;int dp[maxn],w[maxn], n;int root, ans[2];void dfs(int cur){    dp[cur] = w[cur];    for (int i = 0; i < Siz(g[cur]); ++i){        int v = g[cur][i];        dfs(v);        dp[cur] += dp[v];    }    if (dp[cur] == sum && cur != root ){        if (ans[0] == 0) ans[0] = cur,dp[cur] = 0;        else if (ans[1] == 0)ans[1] = cur,dp[cur] = 0;    }}int main(){    scanf("%d",&n);    for (int i = 1; i <= n; ++i){        int u,v;        scanf("%d %d",&u, &v);        g[u].ps(i);        w[i] = v;        if (u == 0) root = i;        sum += v;    }    if (sum % 3) return 0 * puts("-1");    sum /= 3;    dfs(root);    if (ans[0] == 0 || ans[1] == 0) return 0 * puts("-1");    PRintf("%d %d/n",ans[0], ans[1]);    return 0;}/**62 40 -14 22 31 24 5**/
C. Garlandtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Once at New Year Dima had a dream in which he was presented a fairy garland. A garland is a set of lamps, some pairs of which are connected by wires. Dima remembered that each two lamps in the garland were connected directly or indirectly via some wires. Furthermore, the number of wires was exactly one less than the number of lamps.
There was something unusual about the garland. Each lamp had its own brightness which depended on the temperature of the lamp. Temperatures could be positive, negative or zero. Dima has two friends, so he decided to share the garland with them. He wants to cut two different wires so that the garland breaks up into three parts. Each part of the garland should shine equally, i. e. the sums of lamps' temperatures should be equal in each of the parts. Of course, each of the parts should be non-empty, i. e. each part should contain at least one lamp.
Help Dima to find a suitable way to cut the garland, or determine that this is impossible.
While examining the garland, Dima lifted it up holding by one of the lamps. Thus, each of the lamps, except the one he is holding by, is now hanging on some wire. So, you should print two lamp ids as the answer which denote that Dima should cut the wires these lamps are hanging on. Of course, the lamp Dima is holding the garland by can't be included in the answer.
Input
The first line contains single integer n (3?≤?n?≤?106) — the number of lamps in the garland.
Then n lines follow. The i-th of them contain the information about the i-th lamp: the number lamp ai, it is hanging on (and 0, if is there is no such lamp), and its temperature ti (?-?100?≤?ti?≤?100). The lamps are numbered from 1 to n.
Output
If there is no solution, print -1.
Otherwise print two integers — the indexes of the lamps which mean Dima should cut the wires they are hanging on. If there are multiple answers, print any of them.
Examplesinput
62 40 54 22 11 14 2output
1 4input
62 40 64 22 11 14 2output
-1Note
The garland and cuts scheme for the first example: