Garland

题目大意

有一颗 个点的数，第 个点的权值为 ，让你剪掉其中两条边，使得最后得到的三个子树的全职和相等

分析

在 遍历的时候，统计一下子树的权值之和，只要权值之和为总权值的 就可以放到队列里，最后看队列的大小是否大于 ，如果小于 那么显然是无解的情况了，还有如果总权值不是 的倍数，也是无解的
⚠️注意：在输出的时候，只能输出对头，如果不是输出的对头，那么你实际割下来的子树权值之和是有问题的，有兴趣的同学可以自己下来看看

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, cur, cnt, tar, a, rt, t[maxn], ans[5];
int Head[maxn], Edge[maxn], Next[maxn];

inline void addedge(int u, int v)
{
    Next[++cur] = Head[u];
    Head[u] = cur;
    Edge[cur] = v;
}

inline void dfs(int u, int f) 
{
    for (int i = Head[u]; i; i = Next[i]) {
        int v = Edge[i];
        if (v == f) continue;
        dfs(v, u);
        t[u] += t[v];
    }
    if (t[u] == tar) {
        ans[++cnt] = u;
        t[u] = 0;
    }
}

int main()
{
    n = __read();
    for (int i = 1; i <= n; ++i) {
        a = __read(), tar += t[i] = __read();
        if (a) addedge(a, i);
        else rt = i;
    }
    if (tar % 3) return puts("-1") & 0;
    tar /= 3;
    dfs(rt, 0);
    if (cnt < 3) puts("-1");
    else printf ("%d %d\n", ans[1], ans[2]);
}