Description
有一個樹形結(jié)構(gòu)的賓館他爸，n個房間，n-1條無向邊果善，每條邊的長度相同诊笤，任意兩個房間可以相互到達(dá)。吉麗要給他的三個妹子各開（一個）房（間）巾陕。三個妹子住的房間要互不相同（否則要打起來了）讨跟，為了讓吉麗滿意，你需要讓三個房間兩兩距離相同惜论。
有多少種方案能讓吉麗滿意许赃？
Input
第一行一個數(shù)n。
接下來n-1行馆类，每行兩個數(shù)x,y混聊，表示x和y之間有一條邊相連。
Output
讓吉麗滿意的方案數(shù)乾巧。
Sample Input
7
1 2
5 7
2 5
2 3
5 6
4 5
Sample Output
5
HINT
【樣例解釋】
{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}
【數(shù)據(jù)范圍】
n≤5000
先枚舉一個點(diǎn)句喜，然后dfs計數(shù)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5005;
int fi[N],ne[N<<1],j[N<<1];
int n,mx;
long long t1[N],t2[N],s[N],ans;
void dfs(int ro,int fa,int dep){
mx=max(mx,dep);s[dep]++;
for (int u=fi[ro];u;u=ne[u])
if (j[u]!=fa)dfs(j[u],ro,dep+1);
}
int main (){
scanf ("%d",&n);
for (int i=1;i<n;++i){
scanf ("%d%d",&j[i+n],&j[i]);
ne[i]=fi[j[i+n]];fi[j[i+n]]=i;
ne[i+n]=fi[j[i]];fi[j[i]]=i+n;
}
for (int i=1;i<=n;++i){
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
for (int u=fi[i];u;u=ne[u]){
dfs(j[u],i,1);
for (int k=1;k<=mx;++k){
ans+=t2[k]*s[k];
t2[k]+=t1[k]*s[k];
t1[k]+=s[k];
s[k]=0;
}
}
}
printf ("%lld",ans);
return 0;
}
