的卢西奥(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
官方题解:.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);}}
}
更多推荐
喵哈哈村的卢西奥(dfs)
发布评论