题意
给你张无自环无重边的无向连通图， 求有多少种方案加边使得这个图是仙人掌。
(n leq 5 imes 10^5)
题解
牛逼题。
考虑这么搞， 把环上的边断掉因为环上的边肯定没用。然后问题转化到树上， 把所有树的答案乘起来就是答案。
按照套路设(f_x)表示(x)子树内没有向上的边的方案数， (g_x)表示(x)子树内有向上的边的方案数。
如果直接转移， 那么在考虑一个点(x)的儿子的时候， 每条边都不知道是不选还是选， 选出来也不知道如何去配对， 那么配对的时候需要求一个数组(h)表示这么多个点合并起来的方案数， 同时还要使用多项式， 对每个点构造一个多项式(gx + f)然后分治(FFT)求出系数。然后就(n log_2^2 n)了。
但是这里有一个很神奇的转化， 让不被覆盖的边看成自己被覆盖， 那么问题变成了要求每条边都被覆盖。这个问题的话你发现每个儿子必须有边延伸出来， 然后你可以在每个点直接考虑儿子的情况。
具体来说有下面的转移：
[h_i = h_{i - 1} + h_{i - 2} (i - 1) \ f_x = h_{dx}prod_{y in son_x}g_y
\ g_x = prod_{y in son_x}h_{dx} + sum_{y in son_x}g_y imes prod_{z in son_x, z
eq y} g_zh_{dx - 1} =prod_{y in son_x}g_yh_{dx + 1}]
(h)就是用来配对的那个数组。
然后问题就在于判断仙人掌了， 这个可以直接(dfs + stack)， 注意判断是否进入环的时候用(dfn)不要用(vis)！
/*
QiuQiu /qq
____ _ _ __
/ __ (_) | | / /
| | | | _ _ _ | | _ _ / / __ _ __ _
| | | | | | | | | | | | | | | | / / / _` | / _` |
| |__| | | | | |_| | | | | |_| | / / | (_| | | (_| |
\___\_ |_| \__,_| |_| \__, | /_/ \__, | \__, |
__/ | | | | |
|___/ |_| |_|
*/
#include <bits/stdc++.h>
using namespace std;
class Input {
#define MX 1000000
private :
char buf[MX], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
return p1 == p2 ? EOF : *(p1 ++);
}
public :
Input() {
#ifdef Open_File
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
}
template <typename T>
inline Input& operator >>(T &x) {
x = 0; int f = 1; char a = gc();
for(; ! isdigit(a); a = gc()) if(a == '-') f = -1;
for(; isdigit(a); a = gc())
x = x * 10 + a - '0';
x *= f;
return *this;
}
inline Input& operator >>(char &ch) {
while(1) {
ch = gc();
if(ch != '
' && ch != ' ') return *this;
}
}
inline Input& operator >>(char *s) {
int p = 0;
while(1) {
s[p] = gc();
if(s[p] == '
' || s[p] == ' ' || s[p] == EOF) break;
p ++;
}
s[p] = ' ';
return *this;
}
#undef MX
} Fin;
class Output {
#define MX 1000000
private :
char ouf[MX], *p1 = ouf, *p2 = ouf;
char Of[105], *o1 = Of, *o2 = Of;
void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
inline void pc(char ch) {
* (p2 ++) = ch;
if(p2 == p1 + MX) flush();
}
public :
template <typename T>
inline Output& operator << (T n) {
if(n < 0) pc('-'), n = -n;
if(n == 0) pc('0');
while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
while(o1 != o2) pc(* (--o1));
return *this;
}
inline Output & operator << (char ch) {
pc(ch); return *this;
}
inline Output & operator <<(const char *ch) {
const char *p = ch;
while( *p != ' ' ) pc(* p ++);
return * this;
}
~Output() { flush(); }
#undef MX
} Fout;
#define cin Fin
#define cout Fout
#define endl '
'
using LL = long long;
using pii = pair<int, int>;
const int P = 998244353;
inline int Mod(int x) { return x + ((x >> 31) & P); }
inline void pls(int &x, int v) { x = Mod(x + v - P); }
inline void dec(int &x, int v) { x = Mod(x - v); }
const int N = 5e5 + 10;
int n, m;
struct edge {
int to, next;
} e[N * 4];
int cnt = 1, head[N];
int stk[N * 2], top;
int bj[N * 4], vis[N * 2];
void push(int x, int y) {
e[++ cnt] = (edge) {y, head[x]}; head[x] = cnt;
}
int dfn[N];
void clr() {
for(int i = 1; i <= cnt; i ++) bj[i] = dfn[i] = 0;
cnt = 1; for(int i = 1; i <= n; i ++) head[i] = 0, vis[i] = 0;
}
bool flg;
inline void addtag(int i) { bj[i] ++; bj[i ^ 1] ++; if(bj[i] > 1) { cout << 0 << endl; flg = 1; } }
void dfs1(int x, int fx) {
//cerr << x << endl;
dfn[x] = ++ dfn[0];
vis[x] = 1; if(flg) return ;
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to; if(y == fx) continue;
if(! vis[y]) {
stk[++ top] = i; dfs1(y, x); if(flg) return ; top --;
}
else if(dfn[y] < dfn[x]) {
//cerr << "Case" << endl;
//cerr << x << endl;
addtag(i); if(flg) return ;
for(int j = top; j >= 1; j --) {
int p = stk[j];
int now = e[p].to;
addtag(p); if(flg) return ;
if(e[p ^ 1].to == y) break;
}
}
}
}
int f[N], g[N], h[N];
void dfs2(int x, int fx) {
vis[x] = 1;
f[x] = 1; g[x] = 0; int dx = 0;
for(int i = head[x]; i; i = e[i].next) if(! bj[i]) {
int y = e[i].to; if(y == fx) continue;
dfs2(y, x); dx ++;
f[x] = 1ll * f[x] * g[y] % P;
}
g[x] = 1ll * f[x] * h[dx + 1] % P;
f[x] = 1ll * h[dx] * f[x] % P;
}
void solve() {
cin >> n >> m; flg = 0; top = 0;
for(int i = 1, x, y; i <= m; i ++) {
cin >> x >> y;
push(x, y); push(y, x);
}
dfs1(1, 0);
if(flg) {// cerr << 312 << endl;
clr(); return ;
}
for(int i = 1; i <= n; i ++) vis[i] = 0;
h[0] = 1; h[1] = 1;
for(int i = 2; i <= n; i ++) h[i] = (h[i - 1] + 1ll * h[i - 2] * (i - 1) % P) % P;
int ans = 1;
for(int i = 1; i <= n; i ++) if(! vis[i]) {
dfs2(i, 0);
ans = 1ll * ans * f[i] % P;
}
cout << ans << endl;
clr();
}
int main() {
int Case; cin >> Case;
while(Case --) solve();
return 0;
}