BZOJ3522: [Poi2014]Hotel

3522: [Poi2014]Hotel

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 195 Solved: 85
[Submit][Status]

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

HINT

【样例解释】

{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【数据范围】

n≤5000

Source

By Dzy

题解：
这题搞了好久时间。。。
直接贴代码吧，我已经记住这道题了。。。
代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 5000+5

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,tot,head[maxn];

 ll f[maxn][],s[maxn];

 struct edge{int go,next;}e[*maxn];

 inline void insert(int x,int y)

 {

     e[++tot]=(edge){y,head[x]};head[x]=tot;

     e[++tot]=(edge){x,head[y]};head[y]=tot;

 }

 inline void dfs(int x,int fa,int dep)

 {

     s[dep]++;

     for(int i=head[x];i;i=e[i].next)

         if(e[i].go!=fa)dfs(e[i].go,x,dep+);

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     for1(i,n-)insert(read(),read());

     ll ans=;

     for1(x,n)

     {

         for(int i=head[x];i;i=e[i].next)

         {

           dfs(e[i].go,x,);

           for1(j,n)

             if(s[j])

             {

                 f[j][]+=f[j][]*s[j];

                 f[j][]+=f[j][]*s[j];

                 f[j][]+=s[j];

                 s[j]=;

             }

             else break;

         }

         for1(j,n)if(f[j][])ans+=f[j][],f[j][]=f[j][]=f[j][]=;else break;

     }

     printf("%lld\n",ans);

     return ;

 }

比较明显的组合计数用数学来搞比较好，稍微复杂一点的不如用递推式来递推。

UPD:还是写一下题解吧。。。

我们枚举每个点做根，那么合法的方案就是在不同的子树中取出3个dep相同的节点的方案数，每dfs一棵子树，我们就用它的信息来更新ans，注意信息用了就要清空。

秒客网