HDu 4705(ツリーDP)
1本の木にどれだけの3つの点の間に簡単な経路がないことを求めて、簡単な経路は繰り返しの点を歩かないで、小さいbossは私に考えを言った後に、書き間違えて、自分で思いついた方法ではありませんてやはり少し熟知していないで、絵を描いて自分で探して、あげた考えは大きい方向の上ですでに合って、全部でC(n,3)種類の組み合わせがあって、簡単な経路の組み合わせの数を求めるだけでokになりました、任意の点uは中間点であり、現在求められている息子sonの中から1つを選択し、u、残りのすべてのノードn-temp-1(tempはすでに求められたuの息子個数であり、息子と息子の間で繰り返し演算できない)の中から1つを選択し、son*(n-temp-1)種の組み合わせを構成することができる.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
int vis[100010],head[100010],num,n;
__int64 ans;
struct edge
{
int st,ed,next;
}e[200010];
void addedge(int x,int y)
{
e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
int dfs(int u)
{
int i,v,temp=0,f;
vis[u]=1;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(vis[v]==1)continue;
f=dfs(v);//
temp+=f;//
ans+=(__int64)(n-temp-1)*(__int64)f;//
}
return temp+1;
}
int main()
{
int x,y,i;
__int64 sum,a;
while(scanf("%d",&n)!=-1)
{
memset(head,-1,sizeof(head));
num=0;ans=0;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
}
memset(vis,0,sizeof(vis));
dfs(1);
a=n;
sum=a*(a-1)*(a-2)/6;
printf("%I64d
",sum-ans);
}
return 0;
}