HDU 4705:Y 树形DP Y
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4705
题意：
给出一棵树，求集合{A,B,C}的个数，A,B,C均为树的节点且三点不在同一路径上
题解：
求出在同一路径的{A,B,C}的个数X，再用总数减去X就行了
求X可以有两种方法：
①将当前节点V视为路径的中点，则X总数加上（以V为根节点的子树的节点数-1）*（剩余节点数）就行了，这种方法较为简单
②设dp[i]为以 i 为根节点的子树上满足要求的集合数，该值可以由两种方式得到，分别为 i 在路径中和i不在路径中，比较复杂，需要考虑周全
附上②的代码
代码
#include<stdio.h>
#include<string.h>
#include<vector>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const int N=1e5+1;
long long dp[N];
struct node
{
int v,next;
}E[N*4];
int cnt,head[N];
long long sum[N],total[N];
void add(int u,int v)
{
E[cnt].v=v;
E[cnt].next=head[u];
head[u]=cnt++;
}
void clean()
{
memset(head,-1,sizeof(head));
memset(total,0,sizeof(total));
memset(dp,0,sizeof(dp));
cnt=0;
}
void Dfs_TreeDp(int id,int fa)
{
long long sum1=0,sum2=0;
sum[id]=1;
for(int i=head[id];i!=-1;i=E[i].next)
{
int v=E[i].v;
if(v==fa)continue;
Dfs_TreeDp(v,id);
total[id]+=sum[v]+total[v]-1;
sum[id]+=sum[v];
sum1+=sum2*sum[v];
sum2+=sum[v];
}
for(int i=head[id];i!=-1;i=E[i].next)
{
int v=E[i].v;
if(v==fa)continue;
dp[id]+=dp[v]+(sum[v]+total[v]-1)*(sum[id]-sum[v]-1);
}
dp[id]+=sum1+total[id];
}
void solve()
{
int n,a,b;
while(~scanf("%d",&n))
{
clean();
for(int i=1;i<n;++i)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
Dfs_TreeDp(1,1);
long long ans=(long long)n;
ans=ans*(n-1)*(n-2)/6-dp[1];
printf("%lld
",ans);
}
}
int main()
{
solve();
return 0;
}