10月14日Garland(DFS+思维)

思路：
假设我们要组合出来的数是，并且三个部分都是相同的那么总和就是，那么我们可以找到一种为的情况，即每个点的总和如果不是的倍数那么必然输出，如果是三个倍数如果找不到可以切割的两条边也是，注意到这是一棵树那么切割出来必然是类似于三个联通块，所以我们直接dfs计算以每个节点为子树的总和，如果找到满足答案的就记录答案并且它的父节点不记录这个子树的和(即切割),最后输出一下答案就行了。
一开始我是用这个条件判断是否存在答案的，举个反例可以发现当全部节点为并且是可以划分的，把条件改就行了。
代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

const int maxn = 2e6 + 10;
int rt[maxn];
vector<pair<int,int> >G[maxn];
int son[maxn];
int x;
vector<int>ans;
void dfs(int u,int fu){
    //if(ans.size() >= 2)return ;
    son[u] = rt[u];
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i].first;
        int index = G[u][i].second;
        if(v == fu)continue;
        dfs(v,u);
        if(son[v] == x){
            //cout<<u<<" "<<v<<endl;
            ans.push_back(index);
            continue;
        }
        son[u] += son[v];
    }
}
void solved(){
    int n;scanf("%d",&n);int s = 0;
    for(int i = 1; i <= n; i++){
        int a,t;scanf("%d%d",&a,&t);s += t;rt[i] = t;
        if(a == 0)continue;
        G[i].push_back({a,i});
        G[a].push_back({i,i});
    }
    if(s % 3 != 0){
        cout<<"-1"<<endl;
        return ;
    }
    x = s / 3;
    dfs(1,-1);
    if((int)ans.size() >= 2){
        printf("%d %d\n",ans[0],ans[1]);
    }else {
        puts("-1");
    }
}
int main(){
    solved();
    return 0;
}