Garland

Garland

思路

写法比较显然，dfs去判断，是否存在子树所有节点权值相加等于即可
特判一下无法整除的情况和不存在至少两个节点满足上述条件的情况，
直接输出答案就🆗了。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int head[N], to[N], nex[N], cnt = 1;

int value[N], sz[N], n, sum, root;

vector<int> ans;

void add(int x, int y) {
  to[cnt] = y;
  nex[cnt] = head[x];
  head[x] = cnt++;
}

void dfs(int rt, int fa) {
  sz[rt] = value[rt];
  for(int i = head[rt]; i; i = nex[i]) {
    if(to[i] == fa) continue;
    dfs(to[i], rt);
    sz[rt] += sz[to[i]];
  }
  if(rt != root && sz[rt] == sum) {//这颗子树满足条件，把改子树清空，防止对后续的查找造成影响
    sz[rt] = 0;
    ans.push_back(rt);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    int x;
    scanf("%d %d", &x, &value[i]);
    sum += value[i];
    if(!x) {
      root = i;
    }
    else {
      add(x, i);
    }
  }
  if(sum % 3) {
    puts("-1");
    return 0;
  }
  sum /= 3;
  dfs(root, 0);
  if(ans.size() < 2) {
    puts("-1");
  }
  else {
    printf("%d %d\n", ans[0], ans[1]);
  }
  return 0;
}