hdu 4705 树形dp
日期：2011-07-04 浏览次数：20438 次
题意：树上任意三个点不在一条路径上，统计这样的三点集合有多少种。
三个点构成的路方案数 S = C(n,3)=n*(n-1)*(n-2)/6
用S减去三个点在一条路径上的数目就是答案。
枚举中间点作为第二个点，在它的第K棵子树上找一个点作为第一个点，在剩下的，没有枚举过的结点里，找一个点作为第三个点。数目相乘。
这样问题就变成了统计结点的子节点问题，简单的树形dp。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#pragma comment(linker,"/STACk:102400000,102400000")
using namespace std;
vector<int> tree[100005];
typedef long long ll;
ll ans,ll n;
ll dfs(int k,int fa=-1)
{
ll sum=0,son=0;
for(int i=0;i<tree[k].size();i++)
if(tree[k][i]!=fa){
sum+=son=dfs(tree[k][i],k);
ans+=son*(n-sum-1);
}
return sum+1;
}
int main()
{
int a,b;
while(cin>>n)
{
for(int i=1;i<=n;i++) tree[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
tree[a].push_back(b);
tree[b].push_back(a);
}
ans=0;
dfs(1);
cout<<n*(n-1)*(n-2)/6-ans<<endl;
}
return 0;
}
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
