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.4s$？可是我这最坏复杂度 $n^2$ ？

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

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

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

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

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

此时 10:30，开 T4 ！

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

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

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

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

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

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

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

结果是

100 + 100 + 100 + 70 = 370

差点挂分

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

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

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

题解

T3

 

T4

$n\le 12$，注意要用集合划分的方式去搜，不会 TLE

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

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

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

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

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

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

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

就 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 ;
}