喵哈哈村的卢西奥（dfs）

的卢西奥（dfs）"/>

喵哈哈村的卢西奥（dfs）

喵哈哈村的卢西奥

发布时间: 2017年3月14日 20:02   最后更新: 2017年3月14日 20:04   时间限制: 1000ms   内存限制: 128M

为了拯救喵哈哈村，这个世界必须要存在英雄。

一名叫做卢西奥的英雄站了出来！他现在面临一个难题：

他被要求将一棵树拆成3份，使得每一份中所有节点的权值和相等。

他希望知道，对于一棵给定的有根树，在选取其中2个非根节点并将它们与它们的父亲节点分开后，所形成的三棵子树的节点权值之和能够两两相等的方案有多少种。

两种方案被看做不同的方案，当且仅当形成方案的2个节点不完全相同。

每个输入文件包含多组输入，在输入的第一行为一个整数T，表示数据的组数。

每组输入的第一行为一个整数N，表示给出的这棵树的节点数。

接下来N行，依次描述结点1~N，其中第i行为两个整数Vi和Pi，分别描述这个节点的权值和其父亲节点的编号。

父亲节点编号为0的节点为这棵树的根节点。

满足3<=N<=100000, |Vi|<=100, T<=10

对于每组输入，输出一行Ans，表示方案的数量。

2
3
1 0
1 1
1 2
4
1 0
1 1
1 2
1 3

1
0

 C (GCC 4.8)  C++ (G++ 4.3)  Java (Oracle JDK 1.7)

官方题解：.html

#include<math.h>
#include<vector>
#include<stdio.h>  
#include<string.h>  
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 100005
vector<int>q[maxn];
int pre[maxn],a[maxn],b[maxn],t1,t2,sum;
ll ans;
void build(int x)
{pre[x]+=a[x];int i;for(i=0;i<q[x].size();i++){build(q[x][i]);pre[x]+=pre[q[x][i]];}return;
}
void dfs(int x)
{if(pre[x]==sum/3)ans+=t1+t2;if(b[x]!=0 && pre[x]==sum*2/3)t2++;for(int i=0;i<q[x].size();i++)dfs(q[x][i]);if(pre[x]==sum/3)t1++;if(b[x]!=0 && pre[x]==sum*2/3)t2--;
}
int main()
{int T,n,i,root;scanf("%d",&T);while(T--){for(i=0;i<maxn;i++)q[i].clear();sum=0;t1=t2=0;ans=0;memset(pre,0,sizeof(pre));scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);sum+=a[i];q[b[i]].push_back(i);if(b[i]==0)root=i;}if(sum%3)printf("0\n");else{build(root);dfs(root);printf("%lld\n",ans);}}
}