CF767C Garland

传送门

Solution

设所有节点的权重之和为 $tot$，若 $tot$ 不能被 $3$ 整除，则问题无解。

设 $v$ 在以 $u$ 为根的子树中，且以 $v$ 为根的子树权重和为 $\dfrac{n}{3}$，则 $f_u=v$。如果有多个符合要求的 $v$，则 $f_u$ 取任意一个即可。如果 $v$ 不存在，则 $f_u=0$。dp 可求出 $f_u$。当且仅当下面两种情况，问题有解：

1. 设 $v$ 是 $u$ 的儿子，且有两个或以上的 $v$ 满足 $f_v$ 非零。答案为这两个 $f_v$。
2. $f_u$ 非零，且以 $u$ 为根的子树权重和等于 $\dfrac{2n}{3}$。答案为 $u$ 和 $f_u$。

时间复杂度 $O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, a[N], fa[N], sum[N], f[N], tot;
vector<int> g[N];

void dfs(int u)
{
    sum[u] = a[u];
    for (int v : g[u]) {
        dfs(v);
        sum[u] += sum[v];
        if (f[v]) {
            if (!f[u])
                f[u] = f[v];
            else {
                printf("%d %d", f[u], f[v]);
                exit(0);
            }
        }
    }
    if (sum[u] == tot * 2 && f[u] && fa[u]) {
        printf("%d %d", f[u], u);
        exit(0);
    }
    if (sum[u] == tot)
        f[u] = u;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &fa[i], &a[i]);
        g[fa[i]].push_back(i);
        tot += a[i];
    }
    if (tot % 3) {
        printf("-1");
        return 0;
    }
    tot /= 3;
    dfs(g[0][0]);
    printf("-1");
    return 0;
}