树上dfs + 思维

the number lamp ai, it is hanging on (and 0, if is there is no such lamp), 表示的是祖先的序号

链接：点击打开链接

题目中的坑：应该自下而上的判断子树的累加和是否满足条件。如果是自上而下的判断，一旦该树的子树有满足条件的，去掉子树后又满足条件这种情况是无法识别出来。只能一回溯，且实际上回溯的复杂度并不高，相当于遍历所有点两遍。

解析：dfs 判断累加和。如果一个子树满足条件，价值变为零，两棵及以上满足条件则成功（恰好两棵需要额外判断不是根节点）

代码：

#include <bits/stdc++.h>using namespace std;typedef long long ll;int const maxn = 1000006;vector<int>son[maxn];int t[maxn],p,root;int pa[maxn],ans[2];int num = 0;void dfs(int x){    if(num == 2)return;    int temp;    for(int i = 0; i < son[x].size(); i ++)    {        temp = son[x][i];        dfs(temp);        t[x] += t[temp];    }    if(t[x] == p && x != root)    {        ans[num] = x;        num ++;        t[x] = 0;        if(num == 2)return;    }}int main(){   // freopen("in.txt","r",stdin);    int n;    int sum = 0;    scanf("%d",&n);    for(int i = 1; i <= n; i ++)    {        scanf("%d%I64d",&pa[i],&t[i]);        sum += t[i];        son[pa[i]].push_back(i);        if(pa[i] == 0)root = i;    }    bool flag = false;    if(sum % 3 != 0 || sum == 0)    {        flag = true;    }    else    {        p = sum / 3;        dfs(root);        if(num >= 2)        {            PRintf("%d %d/n",ans[0],ans[1]);        }        else        {            flag = true;        }    }    if(flag == true)        printf("-1/n");    return 0;}