CF997D

分析：

　　假设在第一个树上我们有一个长度为x的环，在第二树上我们有一个长度为y的环，那么可以在叉积树上构造出$\binom{x+y}{x}$个长度为x+y的环

　　问题的关键就变成了如何统计出在一个树上的长度为i的环的个数

　　设$f(u,v,k)$表示从u点出发走k步回到u点，中途不经过点v的方案数，其中v是u的相邻点

　　考虑求解的转移过程，一定是从u走到某个邻接点w(w!=v)，然后从w走到w（不经过u），然后再回到u，于是有转移方程

　　这个是$O(n^2k^2)$的，但明显里面的w不需要枚举，只需要拿sum减去w=v的情况就行了，于是变成了$O(nk^2)$

 #include<bits/stdc++.h>

 using namespace std;

 #define mp make_pair

 const int maxn=,mod=;

 int k;

 int ans;

 int C[][];

 void inc(int &a,int b)

 {

     a=(a+b)%mod;

 }

 struct wjmzbmr

 {

     int n;

     vector<int> g[maxn+];

     vector<int> dp[][maxn+];

     int sum[][maxn+];

     int ans[maxn+],sz[maxn+];

     map<pair<int,int>,int> s;

     void init()

     {

         for(int i=;i<n;++i)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             g[u].push_back(v),g[v].push_back(u);

         }

         for(int i=;i<=n;++i)

             for(int j=;j<g[i].size();++j)

                 s[mp(i,g[i][j])]=j;

         for(int i=;i<=n;++i) sz[i]=g[i].size(),g[i].push_back();

         for(int t=;t<=k;++t)

             for(int i=;i<=n;++i)

                 dp[t][i].resize(sz[i]+,);

     }

     void work()

     {

         for(int i=;i<=n;++i)

             for(int j=;j<=sz[i];++j)

             {

                 dp[][i][j]=;

                 inc(sum[][g[i][j]],);

             }

         for(int i=;i<=k;++i)

             for(int u=;u<=n;++u)

                 for(int j=;j<=sz[u];++j)

                 {

                     int v;

                     if(j<sz[u]) v=g[u][j];else v=;

                     int id;

                     if(v==) id=;

                     else

                         id=s[mp(v,u)];

                     for(int t=;t<=i-;++t)

                         dp[i][u][j]=((dp[i][u][j]+1LL*dp[i-t-][u][j]*(sum[t][u]-dp[t][v][id])%mod)%mod+mod)%mod;

                     inc(sum[i][v],dp[i][u][j]);

                 }

         for(int i=;i<=k;i+=)

             for(int u=;u<=n;++u)

                 inc(ans[i],dp[i][u][sz[u]]);

     }

 }tree[];

 int main()

 {

     //freopen("ce.in","r",stdin);

     scanf("%d%d%d",&tree[].n,&tree[].n,&k);

     tree[].init(),tree[].init();

     tree[].work();

     tree[].work();

     C[][]=;

     for(int i=;i<=k;++i)

     {

         C[i][]=;

         for(int j=;j<=i;++j)

             C[i][j]=(C[i-][j]+C[i-][j-])%mod;

     }

     for(int i=;i<=k;++i)

         inc(ans,int(1LL*tree[].ans[i]*tree[].ans[k-i]%mod*C[k][i]%mod));

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

     return ;

 }

巴特西

CF997D

最新文章

热门文章