Description
有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意？
Input
第一行一个数n。
接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。
Output
让吉丽满意的方案数。
Sample Input
7
1 2
5 7
2 5
2 3
5 6
4 5
Sample Output
5
HINT
n≤5000
这题\(O(n^2)\)即可，但是我TM开始想了个巨麻烦的做法。。。直接设\(f[i][j]\)表示深度为\(i\)可以凑出的\(j\)元组的个数，枚举根之后跑3次dfs即可（加强版需要用长链剖分+dp，我不会）
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1;char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=5e3;
int pre[(N<<1)+10],now[N+10],child[(N<<1)+10];
ll f[N+10][4],Ans;
int n,tot;
void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}
void insert(int x,int y){join(x,y),join(y,x);}
void dfs(int x,int fa,int deep,int T){
f[deep][T]+=f[deep][T-1];
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
if (son==fa) continue;
dfs(son,x,deep+1,T);
}
}
void work(int x){
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++) f[i][0]=1;
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p])
dfs(son,x,1,3),dfs(son,x,1,2),dfs(son,x,1,1);
for (int i=1;i<=n;i++) Ans+=f[i][3];
}
int main(){
n=read();
for (int i=1;i<n;i++){
int x=read(),y=read();
insert(x,y);
}
for (int i=1;i<=n;i++) work(i);
printf("%lld\n",Ans);
return 0;
}