LOJ2433. 「ZJOI2018」线图

2023-12-25 14:40:34

题目

正解

参考：
官方题解：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_Tt_T\)就是答案。
为了方便这里\(T\)指有根树。

计算\(w_T\)：
考虑将\(L_k(T)\)的点数算出来，作为\(w_T\)。这时候发现会算多，因为这把\(T\)的联通子图的贡献都算了进去。
于是枚举\(T\)的联通子图\(S\)，计算\(\sum w_S\)，减去即可。
枚举联通子图的时间相比于下面是比较少的，忽略不计。
如果\(k\leq 4\)，可以通过人类智慧将\(L_k(G)\)的点数求出来（此时不需要保证\(G\)是棵树）：
\(k=1\)时，答案为边数。
\(k=2\)时，答案为\(G\)中有多少对相邻的边，于是答案为\(\sum C(deg_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*k^{k-4})\)，其中\(1205\)为大小小于等于\(10\)的本质不同的有根树个数。
有个大优化：做无根树哈希，如果当前的答案之前算过就不用计算。

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

代码

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

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

枚举一棵树的联通子图的时候，先算不包括根的联通子图。设\(sw_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;
}
上一篇：P3469 [POI2008]BLO-Blockade


下一篇：如何在Python中使用aiohttp或asyncio创建并行循环？