dp[S][u] 表示在点集 S 上,以 u 为根的生成树的最优解,此时的点集 S 中的答案必定是已经确定的了,即这个生成树上的所有边都不会再在其他地方有任何改变。
枚举 S 的子集 T ,同时得到 S−T,设为 K,则 S=T+K 。接下来试着把 T 和K 合并,以得到 S :枚举 K 中的点 u ,作为合并后的根节点,则从 u 向 T 中点 v 连边,同时加入边 (u,v) 的贡献,注意,由于上面说的生成树中的边不会再有改变了,所以此时计算贡献应该把全局的贡献都算上,而不仅仅是在点集 S 上的贡献。
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint maxn = 1e6 + 10; const ll mod = 998244353; int n, m; ll qpow(ll a, ll b){ ll res = 1; a %= mod; while (b) { if (b & 1)res = (res * a) % mod; a = (a*a) % mod; b >>= 1; } return res % mod; } int par[maxn], rk[maxn]; ll p[maxn], tot[maxn]; intfind(int x, ll& a, ll& b){ if (par[x] == x) { a = p[x], b = tot[x]; return x; } int fa = find(par[x], a, b); a += p[x], b += tot[x]; return fa; } voidunite(int x, int y){ ll a, b; x = find(x, a, b); y = find(y, a, b); if (x == y)return; p[x]++; tot[x]++; tot[y]++; if (rk[x] > rk[y]) { par[y] = x; p[y] -= p[x]; tot[y] -= tot[x]; } else { par[x] = y; p[x] -= p[y]; tot[x] -= tot[y]; if (rk[x] == rk[y])rk[y]++; } } intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)par[i] = i; for (int i = 0; i < m; i++) { int op; scanf("%d", &op); if (op == 1) { int x, y; scanf("%d%d", &x, &y); unite(x, y); } else { int x; scanf("%d", &x); ll a, b; find(x, a, b); b -= a; ll ans = (qpow(3, n)*qpow(2, a) % mod*qpow(qpow(3, a), mod - 2)) % mod; ans = ans * qpow(qpow(3, b), mod - 2) % mod; printf("%lld\n", ans); } } return0; }