题目分析

题目要求对无向图的每条边定向，使得每个点的出度不超过给定值 (a_i)，求合法方案数。图的特性是每条边至多属于一个简单环（仙人掌图），需结合仙人掌图的结构特性（桥和环）分别处理。

解题思路

1. 仙人掌图分解：使用Tarjan算法将图分解为桥和环，桥属于树边，环属于环边。
2. 动态规划（DP）：
   • 树边处理：对树边进行树形DP，记录每个节点出度为0/1/2的方案数（因环最多贡献2个出度）。
   • 环边处理：对环进行DP，枚举环的定向方式（顺时针或逆时针），统计合法方案数。
3. NTT优化卷积：合并子树DP结果时，使用NTT加速卷积运算，降低时间复杂度。

代码实现（带注释）

#include <bits/stdc++.h>
#define inl inline
#define pb push_back
using namespace std;
typedef vector<int> vc;
const int N = 3e5, P = 998244353, G = 3, IG = 332748118;

// 边结构体（用于Tarjan）
struct E {
    int ne, to;
} ge[N * 2];

vc e[N];          // 分解后的图：e[p]存储p的子节点（桥或环）
int n, m, dc, cnt, top, h[N], a[N];
int dfn[N], low[N], sta[N];  // Tarjan相关数组
int nn, inn, lim, re[N];     // NTT相关参数
int f[N][3];      // f[p][k]：节点p出度为k的方案数（k=0/1/2）
int g[N][2];      // 环DP的临时数组

// 快速读入
inl int Read() {
    int s = 0;
    char c;
    while (!isdigit(c = getchar()));
    for (; isdigit(c); c = getchar())
        s = s * 10 + c - '0';
    return s;
}

// 添加无向边
inl void Add(int x, int y) {
    ge[++dc] = {h[x], y};
    h[x] = dc;
    ge[++dc] = {h[y], x};
    h[y] = dc;
}

// Tarjan算法分解仙人掌图：桥和环
inl void Tarjan(int p, int fr) {
    dfn[p] = low[p] = ++cnt;
    sta[++top] = p;  // 栈存储当前路径节点

    for (int i = h[p], v; i; i = ge[i].ne) {
        if (i == (fr ^ 1)) continue;  // 跳过反向边
        v = ge[i].to;
        if (!dfn[v]) {
            Tarjan(v, i);
            low[p] = min(low[p], low[v]);
            // 找到环：v是环的根
            if (low[v] == dfn[p]) {
                ++dc;  // 新建环节点（编号>n）
                e[p].pb(dc);
                // 弹出环内节点，加入环结构
                for (; sta[top + 1] != v; e[dc].pb(sta[top--]));
            } else if (low[v] > dfn[p]) {
                // 桥：直接加入子节点
                e[p].pb(v);
                --top;
            }
        } else {
            // 回边：更新low值
            low[p] = min(low[p], dfn[v]);
        }
    }
}

// 模加法
inl int Ad(int x, int y) {
    return x + y >= P ? x + y - P : x + y;
}

// 快速幂
inl int Pow(int x, int y) {
    int at = 1;
    for (; y; y >>= 1, x = 1ll * x * x % P)
        if (y & 1)
            at = 1ll * at * x % P;
    return at;
}

// 初始化NTT参数
inl void Init(int n) {
    int er = 0;
    for (nn = 1; nn <= n; nn <<= 1, ++er);
    er = 1 << (er - 1);
    inn = Pow(nn, P - 2);  // nn的逆元
    // 预处理位逆序
    for (int i = 1; i <= nn; ++i)
        re[i] = (re[i >> 1] >> 1) | (i & 1 ? er : 0);
}

// NTT变换
inl void NTT(int *s, bool ty) {
    // 位逆序置换
    for (int i = 1; i <= nn; ++i)
        if (i < re[i])
            swap(s[i], s[re[i]]);
    // 分治处理
    for (int l = 1; l < nn; l <<= 1) {
        int we = Pow(ty ? G : IG, (P - 1) / (l << 1));  // 单位根
        for (int i = 0; i < nn; i += l << 1) {
            for (int j = 0, w = 1, x, y; j < l; ++j, w = 1ll * w * we % P) {
                x = s[i + j];
                y = 1ll * w * s[i + l + j] % P;
                s[i + j] = Ad(x, y);
                s[i + l + j] = Ad(x, P - y);
            }
        }
    }
}

// 多项式乘法（卷积）
inl vc operator *(vc x, vc y) {
    int t = x.size() + y.size() - 1;
    Init(t);
    x.resize(nn);
    y.resize(nn);
    NTT(&x[0], true);   // 正变换
    NTT(&y[0], true);
    // 点乘
    for (int i = 0; i < nn; ++i)
        x[i] = 1ll * x[i] * y[i] % P;
    NTT(&x[0], false);  // 逆变换
    // 乘以逆元，截断长度
    for (int i = 0; i < nn; ++i)
        x[i] = 1ll * x[i] * inn % P;
    x.resize(min(t, lim));
    return x;
}

// 合并子树DP结果（多项式乘法）
inl vc Solve(vector<vc> &s, int l, int r) {
    if (l == r) return s[l];
    int md = (l + r) >> 1;
    return Solve(s, l, md) * Solve(s, md + 1, r);
}

// 递归DP处理节点p
inl vc DP(int p) {
    if (p <= n) {  // 原图节点（桥或环的根）
        vector<vc> s;  // 存储子节点的DP结果
        for (int v : e[p])
            s.push_back(DP(v));
        
        // 叶子节点：无子女
        if (s.empty()) {
            f[p][0] = f[p][1] = 1;  // 出度0/1的方案数为1
            f[p][2] = (a[p] >= 2);  // 出度2的方案数（若a[p]>=2）
            return {1, 1};  // 返回多项式：1 + x
        }

        // 合并子节点的DP结果（卷积）
        lim = a[p] + 1;
        vc t = Solve(s, 0, s.size() - 1);
        lim = min(lim, (int)t.size());

        // 计算f[p][k]：子节点出度和为k的方案数
        memset(f[p], 0, sizeof(f[p]));
        for (int i = 0; i < lim; ++i) {
            for (int j = 0; j <= 2 && i + j <= a[p]; ++j) {
                f[p][j] = Ad(f[p][j], t[i]);
            }
        }

        // 返回多项式：f[p][1] + f[p][0]x（用于父节点计算）
        return {f[p][1], f[p][0]};
    } else {  // 环节点（处理环的定向）
        // 先处理环内每个节点的DP
        for (int v : e[p])
            DP(v);
        
        int t[3] = {0};  // 环的总方案数
        // 枚举环的起始定向（顺时针或逆时针）
        for (int i = 0; i <= 1; ++i) {
            g[0][i] = 1;
            g[0][i ^ 1] = 0;
            // 环DP：逐个处理环内节点
            for (int j = 0; j < (int)e[p].size(); ++j) {
                int v = e[p][j];
                g[j + 1][0] = (1ll * g[j][0] * f[v][1] + 1ll * g[j][1] * f[v][2]) % P;
                g[j + 1][1] = (1ll * g[j][0] * f[v][0] + 1ll * g[j][1] * f[v][1]) % P;
            }
            // 累加环的方案数
            t[1 - i] = Ad(t[1 - i], g[e[p].size()][0]);
            t[2 - i] = Ad(t[2 - i], g[e[p].size()][1]);
        }

        // 返回环的DP结果：t[0] + t[1]x + t[2]x²
        return {t[0], t[1], t[2]};
    }
}

int main() {
    n = Read();
    m = Read();
    dc = 1;  // 边编号从2开始（避免fr^1冲突）
    for (int i = 1; i <= m; ++i)
        Add(Read(), Read());
    for (int i = 1; i <= n; ++i)
        a[i] = Read();
    
    // 分解仙人掌图
    dc = n;  // 环节点编号从n+1开始
    Tarjan(1, 0);
    // 根节点DP
    DP(1);
    // 输出根节点出度为0的方案数（总方案数）
    printf("%d\n", f[1][0]);
    return 0;
}

代码解释

1. 仙人掌图分解：通过Tarjan算法识别桥和环，将图转化为树状结构（环作为虚拟节点）。
2. 树形DP：对每个节点，合并子节点的DP结果（使用NTT加速卷积），统计出度为0/1/2的方案数。
3. 环DP：对环枚举定向方式，计算合法方案数并合并到父节点。
4. 结果输出：根节点出度为0的方案数即为总合法方案数。