11.6 校内模拟赛总结

打的很顺的一场

复盘

7:40 开题，看到题目名很interesting

T1 看起来很典，中位数显然考虑二分，然后就是最大子段和；T2 构造？一看数据范围这么小，感觉不是很难做；T3 神秘数据结构；T4 看到数据范围，这不是我们广义串并联图吗？不过感觉应该有别的做法

7:50 开写，T1 很快过了大样例，感觉不是很能挂

8:00 看 T2，显然有 $2^{n+m}$ 的暴搜，然后先枚举行，每一列的值就定了，然后就是个背包？显然折半搜索。没什么细节，8:40 交了

看 T3，删除操作显然倒过来变成加边； $2$ 操作显然是问是否在一个边双里，可以先把最终状态下边双缩点，然后开始手玩，发现加一条边可以看作把树上两点间路径缩成一个点，这个过程有点抽象啊

上个厕所，冷静一下发现这个其实是能做的，直接从两端点暴力往上跳，每次合并给当前点的父亲，改编号的操作可以启发式来维护。这样就有 $O(n\log n+n\alpha (n))$ 的做法了， $8\times 10^5$ 应该不会卡 $\log$ 吧

9:10 开写了，写完了困难的 tarjan 后猛然意识到图不连通！发现这就有点难做了，合并两棵树是不好做的，树的形态不固定没法找 LCA

再冷静一会，其实我可以把这些树边都保留下来？应该不影响答案，太对了啊

过程中发现启发式根本没必要，并查集直接维护即可

写写写，到最后一步两个点往上跳，先写了个暴力的做法验了验有没有写挂，发现确实挂了

改过后发现满数据竟然只跑 $2.4 s$ ？可是我这最坏复杂度 $n^2$ ？

还是改成复杂度正确的做法了，交了，此时 10:10

本地大样例跑 $2.1 s$ ，不是吧我都没 $\log$ 了还这么慢？考虑卡常

加上了手写快读，本地变成 $1.3 s$ 了，可是时限 $1 s$

尝试输出运行时间，发现光读入就用了 $0.6 s$ ！于是立刻申请超级快读

拿到了超级快读的我发现读入只用 $0.06 s$ ，跑大样例只用 $0.7 s$

此时 10:30，开 T4 ！

发现很唐的 $B (n)$ 做法给了 50pts，然后是树上似乎也不是很难

很快写完了暴搜，发现 $B (n)$ 不仅能跑过 $n = 12$ ， $n = 13, 14$ 也可以

于是启发我们广义串并联图缩完点后直接暴力，发现可以获得比树的做法多整整 10pts 的好成绩

中间又去想了想正解怎么做，类似毒瘤那个题，大概两个方向：要么就是广义串并联图，但缩完点后的暴力得优化一下；要么考虑生成树，然后加边

前者想了很久到最后最快只能得到 $3^n$ 的做法，后者往容斥去想，发现信息根本没法维护，就算按 dfs 序全是返祖边感觉也记录不了

决定写更简单的树，显然直接 $d p$ ，11:40 交了

剩下 20min 写广义串并联也写不完了，就又想了想正解怎么做，无果

结果是

100 + 100 + 100 + 70 = 370

差点挂分

看了赛时提交，T2 同一个做法，用 scanf 的得了 60，用 read 的得了 90，用超级快读的得了 100，逆

发现 T3 其实没必要写 tarjan，直接建最终的那棵最大生成树，然后正常的去缩环就行。( 没事复习了 tarjan 显然不亏啊！

T4 还是没想到正解啊，最后还是有点理不清哪些信息是重要的，需要维护的

题解

T3

在这里插入图片描述

T4

在这里插入图片描述
$n\leq 12$ ，注意要用集合划分的方式去搜，不会 TLE

从树上做法和暴力，我们可以拓展：

考虑往树上加边，不妨认为加的都是返祖边(后来发现这个没什么用)，那么该边的权值与相连两个点的颜色有关

设 $N = m - n + 1$ ，发现这样的点只有 $2 N$ 个，也就是说，我们关注颜色的点只有这么多，剩下的可以在 dp 里算贡献

那么考虑对于这 $2 N$ 个点集合划分，接下来效仿树上做法，设状态 $f_{i,c}$ 表示 $i$ 为 $c$ 颜色时子树地贡献，特别地，若 $c = 0$ ，代表 $i$ 的颜色与划分出的集合都不相同

转移小分讨一下。对于这 $2 N$ 个点的限制，实际上只需把 $f$ 数组的初值特殊赋即可

这个做法的复杂度加上前缀和优化就是 $B (2 N) N n$

进一步优化：是否真的需要 $2 N$ 个点的颜色信息呢？其实不用，对于每条边只要有一个点的颜色枚举即可，另一个点可以在 $d p$ 到这个点时根据颜色直接算贡献，乘到答案里

就 ok 了

int n , m , K ;
struct nn
{
	int x , y , A , B ;
}e[N] ;
LL ksm( LL a , LL b )
{
	LL res = 1 , t = a % mod ;
	while( b ) {
		if( b&1 ) res = res * t % mod ;
		b = b >> 1 ;
		t = t * t % mod ;
	}
	return res ;
}
namespace subtask1
{
	const int N1 = 15 ;
	int w[N1] ;
	LL ans , g[N] ;
	void calc( int cnt )
	{
		LL res = g[cnt] ;
		for(int i = 1 ; i <= m ; i ++ ) {
			if( w[e[i].x]!=w[e[i].y] ) res = res * e[i].A % mod ;
			else res = res * e[i].B % mod ;
		}
		ans = ( ans + res ) % mod ;
	}
	void dfs( int x , int nw )
	{
		if( x == n+1 ) {
			calc(nw) ;
			return ;
		}
		// 新开
		w[x] = nw+1 ;
		dfs( x+1 , nw+1 ) ;
		// 
		for(int i = 1 ; i <= nw ; i ++ ) {
			w[x] = i ;
			dfs(x+1,nw) ;
		}
	}
	void solve()
	{
		g[0] = 1 ;
		ans = 0 ;
		for(int i = 1 ; i <= n ; i ++ ) g[i] = g[i-1]*(K-i+1)%mod ;
		dfs(1,0) ;
		printf("%lld\n" , ans ) ;
	}
}
struct edg
{
	int lst , to , id ;
}E[2*N] ;
int head[N] , tot = 1 ;
inline void add( int x , int y , int id )
{
	E[++tot] = (edg){head[x],y,id} ;
	head[x] = tot ;
}
namespace subtask2
{
	const int M = 5010 ;
	LL f[N][M] , Sum[N] ;
	void dfs( int x , int fa )
	{
		for(int i = 1 ; i <= K ; i ++ ) f[x][i] = 1 ;
		Sum[x] = 0 ;
		for(int i = head[x] ; i ; i = E[i].lst ) {
			int t = E[i].to ;
			if( t == fa ) continue ;
			dfs( t , x ) ;
			for(int j = 1 ; j <= K ; j ++ ) {
				f[x][j] = f[x][j] * (((Sum[t]-f[t][j])*e[E[i].id].A+f[t][j]*e[E[i].id].B)%mod) % mod ;
			}
		}
		for(int i = 1 ; i <= K ; i ++ ) Sum[x] = ( Sum[x] + f[x][i] ) % mod ;
	}
	void solve()
	{
		for(int i = 1 ; i <= m ; i ++ ) {
			add( e[i].x , e[i].y , i ) ;
			add( e[i].y , e[i].x , i ) ;
		}
		dfs( 1 , 0 ) ;
		printf("%lld\n" , (Sum[1]+mod)%mod ) ;
		tot = 0 ;
		memset( head , 0 , sizeof head ) ;
	}
}
namespace subtask3
{
	// emmm 似乎并不依赖返祖边的性质 
	const int M = 15 ;
	int dfn[N] , tim , Y[M] , R , nam[N] ;
	bool tree[N<<1] ;
	void dfs1( int x , int inE )
	{
		dfn[x] = ++tim ;
		for(int i = head[x] ; i ; i = E[i].lst ) {
			if( i==(inE^1) ) continue ;
			int t = E[i].to ;
			if( !dfn[t] ) tree[i] = 1 , dfs1(t,i) ;
			else {
				if( dfn[t]<dfn[x] ) Y[++R] = t ;//返祖边 
			}
		}
	}
	int w[M] , col ;
	LL ans , f[N][M] , Sum[N] ;// 1~col 表示划分出的这几种颜色，0 表示与这些都不同 
	void dfs3( int x , int inE )
	{
		for(int i = 1 ; i <= col ; i ++ ) {
			if( nam[x] ) f[x][i] = 0 ;
			else f[x][i] = 1 ;
		}
		if( nam[x] ) f[x][w[nam[x]]] = 1 , f[x][0] = 0 ;
		else f[x][0] = 1 ;
		Sum[x] = 0 ;
		for(int i = head[x] ; i ; i = E[i].lst ) {
			if( i==(inE^1) ) continue ;
			int t = E[i].to ;
			if( tree[i] ) {
				dfs3( t , i ) ;
				for(int j = 1 ; j <= col ; j ++ ) {
					f[x][j] = ((f[t][0]*(K-col)%mod+Sum[t]-f[t][j])*e[E[i].id].A+f[t][j]*e[E[i].id].B) % mod * f[x][j] % mod ;
				}
				f[x][0] = ((Sum[t]+f[t][0]*max(0,(K-col-1)))%mod*e[E[i].id].A+f[t][0]*e[E[i].id].B)%mod*f[x][0]%mod ;
			}
			else {
				if( dfn[t]<dfn[x] ) {
					int c = w[nam[t]] ;
					for(int j = 1 ; j <= col ; j ++ ) {
						if( j == c ) f[x][j] = f[x][j]*e[E[i].id].B%mod ;
						else f[x][j] = f[x][j]*e[E[i].id].A%mod ;
					}
					f[x][0] = f[x][0]*e[E[i].id].A%mod ;
				}
			}
		}
		for(int j = 1 ; j <= col ; j ++ ) {
			Sum[x] = ( Sum[x] + f[x][j] ) % mod ;
		}
	}
	LL g[N] ;
	void calc( int cnt ) // cnt 个集合 
	{
		col = cnt ;
		dfs3( 1 , 0 ) ;
		for(int j = 1 ; j <= col ; j ++ ) {
			ans = ( ans + f[1][j]*g[col] ) % mod ;
		}
		ans = ( ans + f[1][0]*(K-col)%mod*g[col] ) % mod ;
	}
	void dfs2( int x , int nw )
	{
		if( x == R+1 ) {
			if( nw <= K ) calc(nw) ;
			return ;
		}
		w[x] = nw+1 ;
		dfs2( x+1 , nw+1 ) ;
		for(int i = 1 ; i <= nw ; i ++ ) {
			w[x] = i ;
			dfs2(x+1,nw) ;
		}
	}
	void solve()
	{
		for(int i = 1 ; i <= m ; i ++ ) {
			add( e[i].x , e[i].y , i ) ;
			add( e[i].y , e[i].x , i ) ;
		}
		dfs1( 1 , 0 ) ;
		sort( Y+1 , Y+R+1 ) ;
		R = unique( Y+1 , Y+R+1 ) - (Y+1) ;
		for(int i = 1 ; i <= R ; i ++ ) nam[Y[i]] = i ;
		g[0] = 1 ;
		for(int i = 1 ; i <= n ; i ++ ) g[i] = g[i-1]*(K-i+1)%mod ;
		dfs2( 1 , 0 ) ;
		printf("%lld\n" , (ans+mod)%mod ) ;
		tot = 1 ; tim = 0 ; R = 0 ; ans = 0 ;
		memset( head , 0 , sizeof head ) ; 
		memset( dfn , 0 , sizeof dfn ) ;
		memset( nam , 0 , sizeof nam ) ;
		memset( tree , 0 , sizeof tree ) ;
	}
}
void solve()
{
	scanf("%d%d%d" , &n , &m , &K ) ;
	for(int i = 1 ; i <= m ; i ++ ) {
		scanf("%d%d%d%d" , &e[i].x , &e[i].y , &e[i].A , &e[i].B ) ;
	}
	if( n<=12 ) {
		subtask1::solve() ;
		return ;
	}
	if( m == n-1 ) {
		subtask2::solve() ;
		return ;
	}
	subtask3::solve() ;
}

int main()
{
	freopen("color.in","r",stdin) ;
	freopen("color.out","w",stdout) ;
	int t ;
	scanf("%d" , &t ) ;
	while( t -- ) solve() ;
	return 0 ;
}