思路:
假设我们要组合出来的数是,并且三个部分都是相同的那么总和就是
,那么我们可以找到一种为
的情况,即每个点的总和如果不是
的倍数那么必然输出
,如果是三个倍数如果找不到可以切割的两条边也是
,注意到这是一棵树那么切割出来必然是类似于三个联通块,所以我们直接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; }