题目描述

寻找子树是否满足 子树权值*3 == sum 的情况，如果满足，一定是一种合理的切割方案。

(dfs) $O(n)$

C++ 代码

#include <bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(a) a+1,a+n+1
#define allv(a) a.begin(),a.end()
#define rep(i, a, b) for(int i = a ; i <= b ; i++)
#define per(i, a, b) for(int i = b ; i >= a ; i--)
#define IOSCC ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
ll n, m, k, res;
ll a[N], v[N];
map<ll, ll> mp;
vector<ll> g[N];
vector<ll> ans;
ll sum;

ll dfs(ll u,ll fa){
    ll res = v[u];
    for(auto x : g[u]){
        if(x == fa) continue;
        ll t = dfs(x,u);
        if(t * 3 == sum) ans.pb(x);
        else res += t;
    }
    return res;
}

void solve() {
    cin >> n;
    ll rt;
    rep(i,1,n){
        ll f;
        cin >> f >> v[i];
        sum += v[i];
        g[i].pb(f);
        g[f].pb(i);
        if(f == 0){
            rt = i;
        }
    }
    if(sum % 3 != 0) {
        cout << -1;
        return;
    }
    dfs(rt,0);
    if(ans.size() < 2) cout << -1;
    else cout << ans[0] << " " << ans[1];
}

int main() {
    IOSCC;
    int _ = 1;
//    cin >> _;

    while (_--) {
        solve();
        cout << endl;
    }

    return 0;
}