题目

---

正解

参考： 官方题解：https://blog.csdn.net/qq_16267919/article/details/79675232 https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p4337 （极度推荐这篇博客，讲解得非常详细）

由于上面的那篇博客讲得比较清楚，所以我这里就简单地概括一下： 首先考虑$L_k(G)$中的每个点代表什么： $L_1$中一个点代表$G$中一条边。 $L_2$中一个点代表$G$中相连的两条边。 $L_3$中一个点代表$G$中相连的三条边（长度为$3$的链（包括三元环）、或一个点连出的三条边）。 于是总结出$L_k(G)$中的一个点表示$G$中的$k$条边组成的连通块。 这样表述有些问题，修正一下：$L_k(G)$中的一个点表示$G$中的不超过$k$条边组成的连通块。 并且相同的连通块可能被多个节点表示。 然后又可以发现，对于$G$中的一个连通块$S$，求$L_k(S)$，它恰好是$L_k(G)$的一个连通块。 想要比较好的理解这些性质，建议拿几个样例来手玩一下。上面推荐的那篇博客举的样例不错，手玩一下就能够比较好理解。

由于题目中的$G$是一棵树，所以这也可以转化成不超过$k+1$个点组成的连通块。 枚举一个不超过$k+1$个点的连通块$T$，计算$L_k(T)$中有多少个表示$T$的点，记为$w_T$。然后在$G$中找不同的$T$的个数，记为$t_T$。最后$\sum w_T{t}_T$就是答案。 为了方便这里$T$指有根树。

计算$w_T$： 考虑将$L_k(T)$的点数算出来，作为$w_T$。这时候发现会算多，因为这把$T$的联通子图的贡献都算了进去。 于是枚举$T$的联通子图$S$，计算$\sum w_S$，减去即可。 枚举联通子图的时间相比于下面是比较少的，忽略不计。 如果$k\le 4$，可以通过人类智慧将$L_k(G)$的点数求出来（此时不需要保证$G$是棵树）： $k=1$时，答案为边数。 $k=2$时，答案为$G$中有多少对相邻的边，于是答案为$\sum C(de{g}_i,2)$ $k=3$时，答案为$G$中有多少条长度为$3$的链和一个点连出去三条边的方案数（注意这个每个方案贡献为$3$）。 $k=4$时，考虑$L_4(G)=L_3(L_1(G))$，通过将$L_1(G)$中每个点（对应$G$中一条边）的度数算出来，套进$k=3$的式子中，化一下式子就出来了。 时间复杂度都是$O(点数+边数)$。 具体式子上面推荐的博客有。 $k$更大咋办？暴力算出$L_{k-4}(G)$，然后套用上面的方法算出$L_4(L_{k-4}(G))$。 考虑迭代一次点数大概乘$k$，所以时间复杂度大概为$O(k^{k-4})$，点数大概开到$1e5$，边数我开到了$1e7$（可能可以少些吧）。 于是这一部分为$O(1205\ast k^{k-4})$，其中$1205$为大小小于等于$10$的本质不同的有根树个数。 有个大优化：做无根树哈希，如果当前的答案之前算过就不用计算。

计算$t_T$： 设$f_{i,j}$表示将有根树$j$的根放到$i$节点上，多少种方案。 转移的时候枚举有根树$j$的根的每个儿子所代表的子树，和$i$的儿子匹配。套一个状压DP实现。 这样时间复杂度是$O(1205\ast n\ast 2^k)$ 似乎有点慢，加个小优化：不考虑有根树$j$的根的每个儿子直接是叶子节点的情况。状压DP之后再将叶子结点用个组合数计算贡献。 注意在算的过程中可能会有重复计算的情况，于是对于有根树$j$的根的儿子中，对于每种不同的子树计算相同的个数，答案除以它们的阶乘。（其实也可以在状压的时候不用二进制压表示每个子树选或不选，而是压每种子树用了多少个。这样理论上还快些。） 时间复杂度$O(1205\ast n\ast 2^{\frac{k}{2}})$。

---

代码

8k，我醉了…… 讲一下实现细节（不一定和程序中一样）： 处理不同的有根树，而且还要处理出根的儿子子树的编号。 我程序中的方法从有根树点数小到大枚举，枚举括号序。枚举之后判断儿子子树的编号是否有序，如果不有序就不算。 应该还有一种比较优美的方式：按点数从小到大枚举。枚举直接与根相连的子树的种类，枚举的过程保证编号不上升。然后给枚举出来的子树标号。

无根树哈希大概就是找重心。如果重心有两个就在边中间插一个点。 以其为根求括号序。 由于连出的儿子本是无序的，所以先给连出的儿子的哈希值排序之后再计算。

枚举一棵树的联通子图的时候，先算不包括根的联通子图。设$s{w}_T$表示$T$中所有联通子图的$w$之和，之前已经处理了，直接算。 然后算包括根的联通子图。先求$dfs$序，对于一个点，如果它选，下一个考虑就是它的第一个儿子，否则下一个考虑它子树之外。

最后提醒：模块化！模块化！ （话说那些3k或4k的怎么做到的？）

using namespace std; #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <vector> #include <cassert> #define ll long long const int N=5010; const int mo=998244353; const int inv2=499122177; int n,k; //Section:fac,ifac,C(m,n) ll fac[N],ifac[N]; void initC(int n){ ifac[1]=1; for (int i=2;i<=n;++i) ifac[i]=(mo-mo/i)*ifac[mo%i]%mo; fac[0]=ifac[0]=1; for (int i=1;i<=n;++i){ fac[i]=fac[i-1]*i%mo; ifac[i]=ifac[i-1]*ifac[i]%mo; } } ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;} //Section:Graph struct EDGE{int to;EDGE *las;}; template <int _N,int _M> struct Graph{ int n=_N; EDGE e[_M]; int ne; EDGE *last[_N+1]; void init(int _n=0){n=_n,ne=0,memset(last,0,sizeof(EDGE*)*(n+1));} void link(int u,int v){e[ne]={v,last[u]};last[u]=e+ne++;} }; Graph<N,N*2> G; //Section:Get Rooted Tree map<int,int> id; int cnt; int siz[1300]; vector<int> son[1300]; int lf[1300],same[1300]; //lf:Num of leaves connecting to rt directly //same:Pro of 1/(Num of same subT connecting to rt directly)! int rt_hash(int n,int s){return s*22+2*n-1;} void grt(int x,int k,int sum,int s){ if (sum<0) return; if (x==2*k-2){ if (sum) return; s=(s<<1)+(1<<2*k-1); ++cnt; int p=0,_lf=0,_same=1,lst=0,c=0; for (int i=1,j=1;i<2*k-1;++i){ p+=(s>>i&1?-1:1); if (p==0){ int a=rt_hash(i-j+1>>1,(s&(1<<i+1)-1)>>j); if (id.find(a)==id.end()){son[cnt--].clear();return;} a=id[a]; son[cnt].push_back(a); _lf+=(a==1); if (a==lst) c++; else{ _same=(ll)_same*ifac[c]%mo; lst=a,c=1; } j=i+1; } } _same=(ll)_same*ifac[c]%mo; for (int i=1;i<son[cnt].size();++i) if (son[cnt][i-1]>son[cnt][i]){son[cnt--].clear();return;} int key=rt_hash(k,s); id[key]=cnt; siz[cnt]=k,lf[cnt]=_lf,same[cnt]=_same; return; } grt(x+1,k,sum+1,s); grt(x+1,k,sum-1,s+(1<<x)); } //Sectioon: Hash:Unrooted Tree template <int _N,int _M> void build_ut(int x,int t,int &n,Graph<_N,_M> &G){//build UT by id of RT if (siz[t]==1) return; for (int i=0;i<son[t].size();++i){ ++n,G.link(x,n),G.link(n,x); build_ut(n,son[t][i],n,G); } } int G0,G1,all; template <int _N,int _M> void findG(int x,int fa,Graph<_N,_M> &G,int siz[]){//find center of gravity siz[x]=1; bool is=1; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa){ findG(ei->to,x,G,siz); siz[x]+=siz[ei->to]; is&=(siz[ei->to]<=all>>1); } is&=(all-siz[x]<=all>>1); if (is) (G0?G1:G0)=x; } int *_siz,*_key; bool cmpp(int a,int b){return _siz[a]<_siz[b] || _siz[a]==_siz[b] && _key[a]<_key[b];} template <int _N,int _M> void gethash(int x,int fa,Graph<_N,_M> &G,int siz[],int key[]){ siz[x]=1; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa) gethash(ei->to,x,G,siz,key),siz[x]+=siz[ei->to]; static int p[12]; int cnt=0; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa) p[cnt++]=ei->to; _siz=siz,_key=key; sort(p,p+cnt,cmpp); key[x]=0; for (int i=cnt-1,s=0;i>=0;--i){ key[x]+=key[p[i]]<<s; s+=siz[p[i]]*2; } key[x]=(key[x]<<1)+1; } template<int _N,int _M> int ut_hash(Graph<_N,_M> &G,int n,bool rem=1){//rem:whether G can be changed static int sz[12],key[12]; G0=G1=0,all=n,findG(1,0,G,sz); int rt=G0; if (G1){ ++n,G.last[n]=NULL; G.link(n,G0),G.link(n,G1); for (EDGE *ei=G.last[G0];ei;ei=ei->las) if (ei->to==G1){ei->to=n;break;} for (EDGE *ei=G.last[G1];ei;ei=ei->las) if (ei->to==G0){ei->to=n;break;} rt=n; } gethash(rt,0,G,sz,key); ll res=rt_hash(key[rt],n)*(G1?-1:1); if (!rem && G1){ G.ne-=2; for (EDGE *ei=G.last[G0];ei;ei=ei->las) if (ei->to==n){ei->to=G1;break;} for (EDGE *ei=G.last[G1];ei;ei=ei->las) if (ei->to==n){ei->to=G0;break;} G.last[n--]=NULL; } return res; } int rt_to_ut(int t){ static Graph<11,11*2> G; G.init(siz[t]+1); int n; build_ut(1,t,n=1,G); return ut_hash(G,siz[t]); } //Section: Calc w int w[N],sw[N]; map<int,int> ut_w,ut_sw; Graph<100010,10000010> L[2]; Graph<11,11*2> T,S; template <int _N,int _M> int calc234(Graph<_N,_M> &G,int k){ static int deg[100010]; if (k==0) return G.n; if (k==1) return G.ne/2; memset(deg,0,sizeof(int)*(G.n+1)); for (int i=1;i<=G.n;++i) for (EDGE *ei=G.last[i];ei;ei=ei->las) if (i<ei->to) deg[i]++,deg[ei->to]++; ll r=0; if (k==2){ for (int i=1;i<=G.n;++i) (r+=(ll)deg[i]*(deg[i]-1)%mo*inv2)%=mo; } if (k==3){ for (int i=1;i<=G.n;++i) for (EDGE *ei=G.last[i];ei;ei=ei->las) if (i<ei->to) (r+=(ll)(deg[i]-1)*(deg[ei->to]-1))%=mo; for (int i=1;i<=G.n;++i) (r+=(ll)deg[i]*(deg[i]-1)%mo*(deg[i]-2)%mo*inv2)%=mo; } if (k==4){ for (int i=1;i<=G.n;++i){ ll d2=0; for (EDGE *ei=G.last[i];ei;ei=ei->las){ ll d1=deg[i]+deg[ei->to]-2; d2+=d1-1; } (r+=d2*d2)%=mo; } r=r*inv2%mo; for (int i=1;i<=G.n;++i) for (EDGE *ei=G.last[i];ei;ei=ei->las) if (i<ei->to){ ll d1=deg[i]+deg[ei->to]-2; r=((r-(d1-1)*(d1-1))%mo+mo)%mo; } for (int i=1;i<=G.n;++i) for (EDGE *ei=G.last[i];ei;ei=ei->las) if (i<ei->to){ ll d1=deg[i]+deg[ei->to]-2; (r+=d1*(d1-1)%mo*(d1-2)%mo*inv2)%=mo; } } return r; } template <int _N,int _M> void trans(Graph<_N,_M> &G,Graph<_N,_M> &F){ F.init(G.ne/2); for (int i=1;i<=G.n;++i) for (EDGE *ei=G.last[i];ei;ei=ei->las){ int u=(ei-G.e>>1)+1; for (EDGE *ej=ei->las;ej;ej=ej->las){ int v=(ej-G.e>>1)+1; F.link(u,v),F.link(v,u); } } } int fa[12],in[12],out[12],nowdfn,re[12],num[12]; template<int _N,int _M> void getdfn(int x,Graph<_N,_M> &G){ in[x]=++nowdfn; re[nowdfn]=x; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa[x]) fa[ei->to]=x,getdfn(ei->to,G); out[x]=nowdfn; } template<int _N,int _M> void find_st(int k,int n,Graph<_N,_M> &G,Graph<_N,_M> &S,int &res){ int x=re[k]; if (k>G.n){ if (n<G.n) (res+=ut_w[ut_hash(S,n,0)])%=mo; return; } find_st(out[x]+1,n,G,S,res); num[x]=++n; S.link(num[fa[x]],num[x]); S.link(num[x],num[fa[x]]); find_st(k+1,n,G,S,res); S.ne-=2; S.last[num[fa[x]]]=S.last[num[fa[x]]]->las; S.last[num[x]]=S.last[num[x]]->las; } int calcw(int t){ int key=rt_to_ut(t); if (ut_w.find(key)!=ut_w.end()){ sw[t]=ut_sw[key]; return ut_w[key]; } L[0].init(siz[t]); int tot; build_ut(1,t,tot=1,L[0]); int now=0,las=1; for (int i=1;i<=k-4;++i){ swap(now,las); trans(L[las],L[now]); } ll res=calc234(L[now],4); for (int i=0;i<son[t].size();++i) (sw[t]+=sw[son[t][i]])%=mo; T.init(siz[t]); build_ut(1,t,tot=1,T); nowdfn=0,fa[1]=0,getdfn(1,T); S.init(siz[t]); num[1]=1,find_st(2,1,T,S,sw[t]); res=(res-sw[t]+mo)%mo; ut_sw[key]=(sw[t]+=res)%=mo; return ut_w[key]=res; } //Section:Calc t int t[N]; int f[N][1300]; void dp(int x,int fa){ int d=0; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa) dp(ei->to,x),++d; static ll g[1024]; for (int j=1;j<=cnt;++j){ if (son[j].size()>d){f[x][j]=0;continue;} int p=son[j].size()-lf[j]; memset(g,0,sizeof(ll)*(1<<p)); g[0]=1; for (EDGE *ei=G.last[x];ei;ei=ei->las) if (ei->to!=fa){ int y=ei->to; for (int i=(1<<p)-1;i>=0;--i) for (int k=0;k<p;++k) if (!(i>>k&1)){ int id=son[j][lf[j]+k]; (g[i|1<<k]+=(ll)g[i]*f[y][id])%=mo; } } f[x][j]=(ll)g[(1<<p)-1]*C(d-p,lf[j])%mo*fac[lf[j]]%mo*same[j]%mo; (t[j]+=f[x][j])%=mo; } } int main(){ scanf("%d%d",&n,&k); initC(max(n,k+1)); G.init(n); for (int i=1;i<n;++i){ int u,v; scanf("%d%d",&u,&v); G.link(u,v); G.link(v,u); } if (k<=4){ printf("%d\n",calc234(G,k)); return 0; } for (int i=1;i<=k+1;++i) grt(0,i,0,0); for (int i=1;i<=cnt;++i) w[i]=calcw(i); dp(1,0); ll ans=0; for (int i=1;i<=cnt;++i) (ans+=(ll)w[i]*t[i])%=mo; printf("%lld\n",ans); return 0; }