题目分析

题意理解

我们有一个仙人掌图（每个边最多属于一个简单环），需要计算：

• 从1号城市出发，到每个城市k的所有不重复经过边的路径
• 路径的权值是经过边的喜爱度的乘积
• 求所有这样的路径权值之和

关键难点

1. 仙人掌结构：图由树和环组成，需要特殊处理环
2. 不重复边：路径不能重复经过边
3. 生成函数：需要高效计算所有路径的权值和

算法思路

核心思想：圆方树 + 生成函数

1. 圆方树分解

• 圆点：原图的顶点
• 方点：每个环对应一个方点
• 通过DFS建立圆方树结构

2. 生成函数方法

对于每个节点，定义生成函数：

• way[u]：从父节点到u的所有路径权值和
• coe[u]：从根节点1到u的所有路径权值和

3. 环的特殊处理

对于环，使用分治FFT计算环上路径的生成函数

代码详解

#include <bits/stdc++.h>
#define cs const
#define pb push_back
#define poly vector<int>
#define sz size
#define bg begin
#define rez resize
using namespace std;

namespace IO {
    // 快速读入优化
    cs int Rlen = 1 << 22 | 1;
    inline char gc() {
        static char buf[Rlen], *p1, *p2;
        (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, Rlen, stdin));
        return p1 == p2 ? EOF : *p1++;
    }
    int gi() {
        int x = 0;
        char c = gc();
        bool f = false;
        while (!isdigit(c)) f = c == '-', c = gc();
        while (isdigit(c)) x = (((x << 2) + x) << 1) + (c ^ 48), c = gc();
        return f ? -x : x;
    }
} using namespace IO;

cs int Mod = 998244353;

// 模运算工具函数
int add(int a, int b) { return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b) { return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b) { return 1ll * a * b % Mod; }
void Add(int &a, int b) { a = add(a, b); }
void Mul(int &a, int b) { a = mul(a, b); }
void Dec(int &a, int b) { a = dec(a, b); }
int ksm(int a, int b) {
    int as = 1;
    for (; b; b >>= 1, Mul(a, a))
        if (b & 1) Mul(as, a);
    return as;
}

cs int N = 4e5 + 50;
int n, m, nd;  // nd: 圆方树总节点数
vector<int> G[N];  // 圆方树邻接表

// Tarjan相关
int dfn[N], low[N], tim, frm[N], w[N], wl[N], wr[N];

// 原图邻接表
int fi[N], nxt[N], to[N], we[N], ec = 1;

// 添加原图边
void adde(int x, int y, int z) {
    nxt[++ec] = fi[x], fi[x] = ec, to[ec] = y, we[ec] = z;
    nxt[++ec] = fi[y], fi[y] = ec, to[ec] = x, we[ec] = z;
}

// Tarjan算法构建圆方树
void pre_dfs(int u, int fe) {
    dfn[u] = low[u] = ++tim;
    
    for (int e = fi[u], v; e; e = nxt[e]) {
        if (e ^ fe ^ 1) {  // 避免父边和反向边
            if (!dfn[v = to[e]]) {
                frm[v] = u, w[v] = we[e];  // 记录父节点和边权
                pre_dfs(v, e);
                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], dfn[v]);
                
                // 发现环，创建方点
                if (low[v] >= dfn[u]) {
                    G[u].pb(++nd);  // 添加方点
                    
                    // 将环上的点连接到方点
                    for (int t = v, r = we[e]; t != u; t = frm[t]) {
                        wl[t] = r;  // 左边权值
                        wr[t] = r = w[t];  // 右边权值
                        G[nd].pb(t);  // 连接环上点到方点
                    }
                }
            }
        }
    }
    
    // 树边连接
    if (low[u] == dfn[u]) 
        G[frm[u]].pb(u);
}

int way[N], coe[N];  // way: 局部生成函数, coe: 全局系数

namespace Poly {
    cs int K = 18, N = 1 << K | 5;
    int up, bit, *w[K], rv[N];
    
    // 初始化NTT
    void NTT_init() {
        for (int i = 0; i < K; i++)
            w[i] = new int[1 << i];
            
        int wn = ksm(3, (Mod - 1) / (1 << K));
        w[K - 1][0] = 1;
        for (int i = 1; i < (1 << (K - 1)); i++)
            w[K - 1][i] = mul(w[K - 1][i - 1], wn);
            
        for (int i = K - 2; ~i; i--)
            for (int j = 0; j < (1 << i); j++)
                w[i][j] = w[i + 1][j << 1];
    }
    
    void init(int d) {
        up = 1, bit = 0;
        while (up < d) up <<= 1, ++bit;
        for (int i = 0; i < up; i++)
            rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    }
    
    // 快速数论变换
    void dft(poly &a) {
        for (int i = 0; i < up; i++)
            if (i < rv[i]) swap(a[i], a[rv[i]]);
            
        for (int i = 1, l = 0; i < up; i <<= 1, ++l)
            for (int j = 0; j < up; j += (i << 1))
                for (int k = 0, x, y; k < i; k++) {
                    x = a[k + j], y = mul(w[l][k], a[k + j + i]);
                    a[k + j] = add(x, y), a[k + j + i] = dec(x, y);
                }
    }
    
    void idft(poly &a) {
        dft(a);
        reverse(a.bg() + 1, a.end());
        for (int i = 0, iv = ksm(up, Mod - 2); i < up; i++)
            Mul(a[i], iv);
    }
    
    // 多项式乘法
    poly operator * (poly a, poly b) {
        int d = a.sz() + b.sz() - 1;
        
        // 小规模直接计算
        if (a.sz() <= 32 || b.sz() <= 32) {
            poly c(d);
            for (int i = 0; i < a.sz(); i++)
                for (int j = 0; j < b.sz(); j++)
                    Add(c[i + j], mul(a[i], b[j]));
            return c;
        }
        
        // 使用NTT加速
        init(d), a.rez(up), b.rez(up);
        dft(a), dft(b);
        for (int i = 0; i < up; i++) Mul(a[i], b[i]);
        idft(a), a.rez(d);
        return a;
    }
    
    // 特殊多项式操作
    poly decmul(poly a, poly b) {
        int n = a.sz(), m = b.sz(), d = n - m + 1;
        assert(d >= 0);
        reverse(b.bg(), b.end());
        a = a * b;
        for (int i = 0; i < d; i++) a[i] = a[i + m - 1];
        return a.rez(d), a;
    }
    
    // 线段树分治计算环的生成函数
    #define mid ((l+r)>>1)
    poly t[N << 2], F[N << 2];
    
    void cope(int x, int l, int r, cs poly &z) {
        F[x].clear();
        if (l == r) {
            F[x].pb(1), F[x].pb(way[z[l]]);
            return;
        }
        cope(x << 1, l, mid, z), cope(x << 1 | 1, mid + 1, r, z);
        F[x] = F[x << 1] * F[x << 1 | 1];
    }
    
    void _cope(int x, int l, int r, cs poly &z) {
        if (l == r) return coe[z[l]] = t[x][0], void();
        t[x << 1] = decmul(t[x], F[x << 1 | 1]);
        t[x << 1 | 1] = decmul(t[x], F[x << 1]);
        _cope(x << 1, l, mid, z), _cope(x << 1 | 1, mid + 1, r, z);
    }
    #undef mid
    
    // 处理环的生成函数
    int work(cs vector<int> &z) {
        if (z.empty()) return 1;
        
        int n = z.sz();
        cope(1, 0, n - 1, z);  // 构建生成函数线段树
        
        t[1].rez(n);
        t[1][0] = 1;
        for (int i = 1; i < n; i++) 
            t[1][i] = mul(t[1][i - 1], i);
            
        // 计算环的总贡献
        int ans = mul(F[1][n], mul(t[1][n - 1], n));
        for (int i = 0; i < n; i++)
            Add(ans, mul(t[1][i], F[1][i]));
            
        _cope(1, 0, n - 1, z);  // 分发系数
        return ans;
    }
}

// 第一遍DFS：自底向上计算way[]
void calc_dfs(int u) {
    for (int v : G[u]) calc_dfs(v);  // 先处理子节点
    
    if (u <= n) {  // 圆点
        static vector<int> z;
        z.clear();
        
        // 收集方点子节点
        for (int v : G[u]) 
            if (v > n) z.pb(v);
            
        // 计算该点的生成函数
        way[u] = Poly::work(z);
        
        // 更新树边子节点的系数
        for (int v : G[u])
            if (v <= n) 
                coe[v] = mul(way[u], w[v]);
                
    } else {  // 方点（环）
        // 环的总生成函数 = 2 * 环上最后边的权值 * 所有子节点生成函数的乘积
        way[u] = mul(2, wr[G[u].back()]);
        for (int v : G[u])
            Mul(way[u], mul(wl[v], way[v]));
    }
}

// 第二遍DFS：自顶向下计算coe[]
void fin_dfs(int u) {
    if (u <= n) {  // 圆点
        for (int v : G[u]) 
            Mul(coe[v], coe[u]);
    } else {  // 方点
        static int pr[N], sf[N];
        int sz = G[u].sz();
        
        // 前缀积
        pr[0] = wl[G[u][0]];
        for (int i = 1; i < sz; i++)
            pr[i] = mul(pr[i - 1], mul(way[G[u][i - 1]], wl[G[u][i]]));
            
        // 后缀积  
        sf[sz - 1] = wr[G[u].back()];
        for (int i = sz - 2; ~i; i--)
            sf[i] = mul(sf[i + 1], mul(way[G[u][i + 1]], wr[G[u][i]]));
            
        // 分发系数到环上各点
        for (int i = 0; i < sz; i++)
            coe[G[u][i]] = mul(coe[u], add(pr[i], sf[i]));
    }
    
    for (int v : G[u]) fin_dfs(v);
}

int main() {
    nd = n = gi(), m = gi();
    Poly::NTT_init();  // 初始化NTT
    
    // 读入图
    for (int i = 1, u, v, w; i <= m; i++) {
        u = gi(), v = gi(), w = gi();
        adde(u, v, w);
    }
    
    // 构建圆方树
    pre_dfs(1, 0);
    
    // 两遍DFS计算答案
    calc_dfs(1);
    coe[1] = 1;
    fin_dfs(1);
    
    // 输出结果：way[i] * coe[i] 即为从1到i的所有路径权值和
    for (int i = 1; i <= n; i++)
        cout << mul(way[i], coe[i]) << '\n';
        
    return 0;
}

算法核心要点详解

1. 圆方树构建

• 圆点：原图顶点 (1~n)
• 方点：每个环对应一个方点 (n+1~nd)
• 通过Tarjan算法在DFS过程中识别环并创建方点

2. 生成函数定义

• way[u]：从父节点到u的所有不重复边路径的权值和
• coe[u]：从根节点1到u的路径上，除u本身外其他部分的权值乘积

最终答案 = way[u] × coe[u]

3. 环的特殊处理

对于环上的点，路径可以沿两个方向走：

• 顺时针方向：使用前缀积 pr[i]
• 逆时针方向：使用后缀积 sf[i] 环的总贡献 = 顺时针 + 逆时针

4. 分治FFT优化

对于环上多个点的生成函数合并，使用线段树分治 + FFT加速多项式乘法。

复杂度分析

• 圆方树构建：O(n + m)
• 生成函数计算：O(n log² n) 使用分治FFT
• 总复杂度：可以处理 n ≤ 10⁵ 的数据

总结

这道题综合运用了：

1. 圆方树分解 处理仙人掌图
2. 生成函数 计数所有路径
3. 分治FFT 高效计算多项式乘积
4. 动态规划 在树上递推计算

是一个很好的图论与生成函数结合的问题，考察了对复杂图结构的处理能力和多项式技巧的运用。