「BZOJ3522」[POI2014] Hotel
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
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
题解
暴力。。。
枚举三个点的中心
依次对其各子树暴力
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0,f=1;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; } int n,mx,cnt; int last[5005],deep[5005],tmp[5005]; ll s1[5005],s2[5005],ans; struct edge{ int to,next; }e[10005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs(int x,int fa) { mx=max(deep[x],mx); tmp[deep[x]]++; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { deep[e[i].to]=deep[x]+1; dfs(e[i].to,x); } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } for(int x=1;x<=n;x++) { memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); for(int i=last[x];i;i=e[i].next) { deep[e[i].to]=1; dfs(e[i].to,x); for(int j=1;j<=mx;j++) { ans+=s2[j]*tmp[j]; s2[j]+=tmp[j]*s1[j]; s1[j]+=tmp[j]; } for(int j=1;j<=mx;j++) tmp[j]=0; } } printf("%lld\n",ans); return 0; } |
Subscribe
计数器 9863379
OI 课件=>
OI 课件=>