自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:27:02，当前版本为作者最后更新于2020-12-25 16:33:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

瞎几把写的乱搞。

首先拿那个 maker 玩一玩，可以发现环数一般都很小，随了蛮久好像最大就 7 的样子。

所以可以把涉及到的 14 个点拿出来，枚举选/不选，树形背包。

然后这样是 $\mathcal O(4^{cnt}\cdot n)$ 的，过不去。

然后可以发现一般是不连通的，有效的连通块大小大概是几千的样子（具体多少我不记得了）然后只对这些连通块 dp，印象中可以跑到比较后的点了，但还是过不去。

然后可以发现每条环边都是返祖边的，那么有效枚举量只有 $3^{cnt}$ 的，先枚举每条返祖边贡献/不贡献，对于不贡献的情况只需要枚举儿子的选择情况。

复杂度就是 $\mathcal O(3^{cnt}\cdot \textrm{size})$ 了。$\rm size$ 是涉及到的树的大小，$cnt$ 是环数。

代码很丑，修修补补过的。

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define mp make_pair
#define pi pair<int, int>
#define pb push_back
#define vi vector<int>
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int inf = 1e14 + 7 ; 
const int P = 1e9 + 7 ; 
const int N = 2e5 + 5 ; 
const int M = 30 ; 
int n, m, cnt, A[N], Ans, dp[N][2], zk[N], zt[N], g[N], rt[N] ; 
int head[N], fa[N], st[M], top, c[M], zmy, f[N] ;
int ban[N] ; 
struct E {
	int to, next, w ; 
} e[N] ; 
map<pi, int> S ;
struct node {
	int x, y, z ; 
};
node ST[15] ; int num ; 
int fd(int x) {
	return (fa[x] == x) ? fa[x] : fa[x] = fd(fa[x]) ; 
}
void add(int x, int y, int z) {
	e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt,
	e[++ cnt] = (E){ x, head[y], z }, head[y] = cnt ; 
}
void merge(int x, int y, int zz) {	
	int u = fd(x), v = fd(y) ;
	fa[u] = v, add(x, y, zz) ; 
} 
int dfn[N], color ; 
void dfs(int x, int ff) {
	zk[x] = 1 ; 
	Next( i, x ) {
		int v = e[i].to ; if(v == ff) continue ; 
		if(ban[i]) continue ; 
		dfs(v, x) ; 
		dp[x][0] += max(dp[v][1], dp[v][0]) ;
		dp[x][1] += max(dp[v][1] - e[i].w, dp[v][0]) ; 
	}
}
void Dfs(int x, int ff) {
	dfn[x] = ++ color ;
	if(x == ff) rt[x] = 1 ;  
	Next( i, x ) {
		int v = e[i].to ; if(v == ff) continue ; 
		if( !dfn[v] ) Dfs( v, x ), g[x] |= g[v] ;
		else if(dfn[v] < dfn[x]) 
		ST[++ num] = (node){v, x, e[i].w}, ban[i] = 1, ban[i ^ 1] = 1, g[x] = 1 ; 
	}
}
int h[N], qls, cc[100], ttop ; 
int root[N], fgo ; 
signed main()
{
	int xx, yy, zz ; cnt = 1 ; 
	n = gi(), m = gi(), xx = gi(), yy = gi(), A[0] = gi(), zz = gi() ; 
	rep( i, 1, n ) A[i] = (A[i - 1] * 101 + 137) % P ; 
	rep( i, 1, n ) fa[i] = i ; 
	rep( i, 1, m ) {
		xx = (xx * 101 + 137) % P, yy = (yy * 101 + 137) % P,
		zz = (zz * 101 + 137) % P ; 
		int x = xx % n + 1, y = yy % n + 1 ; 
		if(!S[mp(x, y)] && (x != y)) 
			S[mp(x, y)] = S[mp(y, x)] = 1, merge(x, y, zz) ; 
	}
	rep( i, 1, n ) if(!dfn[i]) Dfs(i, i) ; 
	for(re int i = 1; i <= num; ++ i)
	st[++ top] = ST[i].x, st[++ top] = ST[i].y ; 
	sort(st + 1, st + top + 1) ; 
	rep( i, 1, top ) if(st[i] != st[i - 1]) c[++ zmy] = st[i] ; 
	int limit = (1 << zmy) - 1 ; 
	rep( i, 1, zmy ) f[c[i]] = 1 ; 
	int SA = 0 ; 
	rep( i, 1, n ) dp[i][0] = 0, dp[i][1] = A[i] ;
	rep( i, 1, n ) if(rt[i] && (!g[i])) dfs(i, i), SA += max(dp[i][0], dp[i][1]) ; 
	rep( i, 1, n ) if(!zk[i]) h[++ qls] = i ; 
	rep( i, 1, n ) if(!zk[i] && rt[i]) root[++ fgo] = i ; 
	limit = (1 << num) - 1 ; 
	for(re int AC = 0; AC <= limit; ++ AC) {
		int fSA = SA ; 
		rep( j, 1, zmy ) zt[c[j]] = 0 ;
		for(re int j = 1; j <= num; ++ j) {
			if(AC & (1 << (j - 1))) 
			fSA -= ST[j].z, zt[ST[j].x] = 1, zt[ST[j].y] = 1 ; 
		}
		int lim = (AC ^ limit) ; 
		for(re int T = lim; ; T = (T - 1) & lim) {
			rep( i, 1, qls ) zk[h[i]] = 0, dp[h[i]][1] = A[h[i]], dp[h[i]][0] = 0 ; 
			rep( j, 1, zmy ) if(zt[h[j]]) dp[h[j]][0] = -inf ; 
			rep( j, 1, num ) {
				if(!((1 << (j - 1)) & lim)) continue ; 
				if((1 << (j - 1)) & T) 
				dp[ST[j].x][0] = -inf, dp[ST[j].y][1] = -inf ; 
				else 
				dp[ST[j].x][1] = -inf ; 
			}
			int ans = fSA ; 
			rep( i, 1, fgo ) dfs(root[i], root[i]), ans += max( dp[root[i]][0], dp[root[i]][1] ) ; 
			Ans = max(Ans, ans) ; 
			if(!T) break ; 
		}
	}
	cout << Ans << endl ; 
	return 0 ;
}