P6790 [SNOI2020] 生成树
TernaryTree · · 题解
广义串并联图。
给每条边两个值
考虑广义串并联图的三种操作。
-
去除一个度数为
1 的点显然，这个点只能通过这条唯一的出边出去与生成树连通，所以这条边必选，令
ans\gets ans\times f_e 。 -
将一个度数为
2 的点的两端合并，并且去掉自己（串联）原来
(u,v_1) 和(u,v_2) 的两条边记作e_1 和e_2 ，将(v_1,v_2) 合并起来连的新边记作e' 。则有：\begin{aligned}f_{e'}&=f_{e_1}\cdot f_{e_2}\\g_{e'}&=f_{e_1}\cdot g_{e_2}+g_{e_1}\cdot f_{e_2}\end{aligned} -
合并两条重边（并联）
将两条重边记为
e_1,e_2 ，合并后的新边记为e' 。则有：\begin{aligned}f_{e'}&=f_{e_1}\cdot g_{e_2}+g_{e_1}\cdot f_{e_2}\\g_{e'}&=g_{e_1}\cdot g_{e_2}\end{aligned}
由广义串并联图性质我们得到，最后一定只剩下一个点。此时的
用类似拓扑的东西去做一下就行了。删边/加边使用 unordered_map<int, unordered_map<int, pair<int, int>>> 这样的邪恶东西维护，实际上是支持遍历一个点出边的邻接矩阵。
#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second
#define umap unordered_map
//#define cin fin
//#define cout fout
using namespace std;
struct ios {
inline char read() {
static const int inlen = 1 << 18 | 1;
static char buf[inlen], *s, *t;
return (s == t) && (t = (s = buf) + fread(buf, 1, inlen, stdin)), s == t ? -1 : *s++;
}
template<typename T> inline ios& operator>> (T &x) {
static char c11, boo;
for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
if (c11 == -1) return *this;
boo |= c11 == '-';
}
for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
boo && (x = -x);
return *this;
}
} fin;
struct exios {
template<typename _CharT, typename _Traits = char_traits<_CharT>>
struct typ {
typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
};
template<typename T> friend exios &operator<<(exios &out, T num) {
if (num < 0) putchar('-'), num = -num;
if (num >= 10) out << num / 10;
putchar(num % 10 + '0');
return out;
}
friend exios &operator<<(exios &out, const char * s) { printf("%s", s); return out; }
friend exios &operator<<(exios &out, string s) { cout << s; return out; }
friend exios &operator<<(exios &out, typ<char>::end e) { puts(""); return out; }
} fout;
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int n, m, ans = 1;
umap<int, umap<int, pii>> g;
int deg[maxn];
queue<int> q;
void add_edge(int u, int v, pii w) {
if (g.find(u) != g.end() && g[u].find(v) != g[u].end()) {
pii nw = {(w.fs * g[u][v].sc % mod + w.sc * g[u][v].fs % mod) % mod, w.sc * g[u][v].sc % mod};
deg[u]--;
g[u][v] = nw;
} else if (g.find(u) != g.end()) {
g[u][v] = w;
} else {
g[u] = umap<int, pii> ();
g[u][v] = w;
}
}
signed main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
add_edge(u, v, {1, 1});
add_edge(v, u, {1, 1});
++deg[u], ++deg[v];
}
for (int i = 1; i <= n; i++) if (deg[i] <= 2) q.push(i);
while (!q.empty()) {
int u = q.front(), dg = deg[u];
q.pop();
if (!dg) continue;
if (dg == 1) {
pair<int, pii> nxt = *g[u].begin();
int v = nxt.fs;
pii w = nxt.sc;
g[u].erase(v);
g[v].erase(u);
ans = ans * w.fs % mod;
deg[u]--, deg[v]--;
if (deg[v] <= 2) q.push(v);
} else if (dg == 2) {
pair<int, pii> nxt[2] = {};
int v[2] = {};
pii w[2] = {};
int cnt = 0;
for (auto it : g[u]) {
nxt[cnt] = it;
v[cnt] = it.fs;
w[cnt] = it.sc;
g[v[cnt]].erase(u);
cnt++;
}
g[u].clear();
add_edge(v[0], v[1], {w[0].fs * w[1].fs % mod, (w[0].fs * w[1].sc % mod + w[1].fs * w[0].sc % mod) % mod});
add_edge(v[1], v[0], {w[0].fs * w[1].fs % mod, (w[0].fs * w[1].sc % mod + w[1].fs * w[0].sc % mod) % mod});
if (deg[v[0]] <= 2) q.push(v[0]);
if (deg[v[1]] <= 2) q.push(v[1]);
}
}
cout << ans << endl;
return 0;
}