# Bzoj3522 [poi2014]hotel

Posted by yjjr's blog on February 6, 2018

Description

Input

Output

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}
【数据范围】
n≤5000

Source

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5006;
struct edge{int to,next;}e[maxn<<1];

inline void dfs(int x,int fa)
{
mx=max(mx,deep[x]);
num[deep[x]]++;
reg(x){
if(e[i].to==fa)continue;
deep[e[i].to]=deep[x]+1;
dfs(e[i].to,x);
}
}

int main()
{
rep(i,1,n-1){
}
rep(x,1,n){
mem(s1,0),mem(s2,0);
reg(x){
deep[e[i].to]=1;
dfs(e[i].to,x);
rep(j,1,mx){
ans+=s2[j]*num[j];
s2[j]+=num[j]*s1[j];
s1[j]+=num[j];
num[j]=0;
}
}
}
printf("%lld\n",ans);
return 0;
}