3522: [Poi2014]Hotel
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 304 Solved: 156
[Submit][Status][Discuss]
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
Source
因为是三个点之间距离相同。，。所以三个点不可能在一条链上。。只有可能为深度相同的点。。然后知道这点就可以DP了
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 5010;
struct data{ll x,y,next;} e[N<<1];
ll head[N],t1[N],t2[N],tmp[N],deep[N],Max,x,y,cnt,n,ans;
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(ll x,ll y){
e[++cnt].x = x;e[cnt].y = y;
e[cnt].next = head[x];head[x] = cnt;
}
void dfs(ll x,ll fa){
Max = max(Max,deep[x]);
tmp[deep[x]]++;
for (ll i=head[x];i;i=e[i].next)
if (e[i].y!=fa) {deep[e[i].y] = deep[x]+1;dfs(e[i].y,x);}
}
int main(){
n = read();
for (ll i=1;i<n;i++){
x = read();y = read();
Insert(x,y);Insert(y,x);
}
for (ll x=1;x<=n;x++){
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
Max = 0;
for (ll i=head[x];i;i=e[i].next){
deep[e[i].y] = 1;
dfs(e[i].y,x);
for (ll j=1;j<=Max;j++){
ans+=t2[j]*tmp[j];
t2[j]+=t1[j]*tmp[j];
t1[j]+=tmp[j];
}
for (ll j=1;j<=Max;j++) tmp[j] = 0;
}
}
printf("%lld",ans);
}
2025年3月25日 21:39
Awesome! I appreciate your contribution to this matter. It has been useful. my blog: how to finger a girl 바카라 사이트