题意：在一个树上，问能否切两刀，使得三块的节点值的和相同。
思路：
由于这个总的节点和是不变的，每块的节点值和sum固定，dfs搜索，和等于sum/3，切。若不能分成三块（不能被3整除，-1）。
还要判断，切掉的不能是根节点（一条链的情况），还要虽然是3的倍数，但不能切成三个的情况。
ac代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <list> #include <iterator> #include <cmath> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue #define Pll pair<ll,ll> #define Pii pair<int,int> #define fi first #define se second #define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) typedef long long ll; typedef unsigned long long ull; /*-----------------show time----------------*/ const int maxn = 1e6+9; vector<int>mp[maxn]; int a[maxn],s[maxn],n,h,sum = 0; int cnt[3],tot = 0; void dfs(int u,int p) { s[u] = a[u]; for(int i=0; i<mp[u].size(); i++) { int v = mp[u][i]; if(v!=p) { dfs(v,u); s[u] += s[v]; } } if(s[u]==sum) { s[u] = 0; cnt[tot++] = u; } } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++) { int x; scanf("%d%d", &x, a+i); if(x==0)h = i; else mp[x].pb(i); sum += a[i]; } if(sum%3!=0) { puts("-1"); } else { sum = sum / 3; dfs(h,-1); if(cnt[0]==h||cnt[1]==h||tot<=2) { puts("-1"); } else printf("%d %d ",cnt[0],cnt[1]); } return 0; }