[Medium] QOJ9539 Disrupting Communications

简要题意

给定一个 $n$ 个点的树，有 $q$ 次询问，每次询问给出 $u,v$，你需要求出树上有多少个连通块，使得该连通块与路径 $(u,v)$ 无交。答案对 $998,244,353$ 取模。

$2\leq n\leq 10^5,1\leq q\leq 10^5$。

思路

想到了与传统做法不同的方法，感觉这个东西比官方题解的好做很多。

对于每一个询问，不妨假设 $u$ 为根节点，如果记 $f_i$ 表示以 $i$ 为根的连通块数量，那么询问 $(u,v)$ 的答案就是：

$$\sum_{x\in[1,n],x\not\in\mathrm{Path}(u,v)} f_x$$

于是只需要推导出 $f$ 的状态转移方程，就可以得到一个 $O(nq)$ 的朴素做法。

这个状态转移方程也是非常的简单：

$$f_u=\prod_{v\in\mathrm{son}(u)} (f_v+1)$$

上面的做法非常简单，可惜无法通过本题，我们需要更好的做法。

注意到这个 dp 实际上是可以换根的（但是要注意换根时，可能出现 $f_u+1\equiv0\pmod{998244353}$ 的情况，此时 $f_u+1$ 没有逆元，这时可以借鉴 P4692 [Ynoi Easy Round 2016] 谁的梦 的经典技巧，记录有多少个 $0$ 因子来实现。具体可以参考代码中的 magic 结构体），那么自然可以想到跑一遍换根 dp，预先将所有询问离线，挂在树的节点上，那么只需要做到快速对满足要求的点的 dp 值求和，就可以解决本题了。

注意到刻画 $x\not\in\mathrm{Path}(u,v)$ 是相当困难的，但是刻画 $x\in\mathrm{Path}(u,v)$ 是相对容易的，可以正难则反，改为（单点修改）路径求和，这可以用重链剖分配合一个支持单点修改区间查询的数据结构（比如树状数组）实现。

时间复杂度 $O(n\log n+q\log^2 n)$。采用 LCT 或者全局平衡二叉树换掉重链剖分，可以做到 $O((n+q)\log n)$ 不过没有必要。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int A(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int S(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int M(int x, int y){ return 1ll * x * y % mod; }
int P(int x, int y){ int ans = 1; for(;y;x=M(x,x),y>>=1) if(y & 1) ans = M(ans, x); return ans; }
int I(int x){ return P(x, mod - 2); }

const int N = 1e5 + 5;
int n, q, fa[N], dep[N], top[N], siz[N], son[N], seg[N];
vector<int> g[N];

void dfs1(int u){
    siz[u] = 1;
    for(int v : g[u]){
        dep[v] = dep[u] + 1, dfs1(v);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u){
    seg[u] = ++seg[0];
    if(son[u]) top[son[u]] = top[u], dfs2(son[u]);
    for(int v : g[u]){
        if(v != son[u]) top[v] = v, dfs2(v);
    }
}

struct BIT {
    int t[N];
    
    void update(int p, int v){
        for(;p<=n;p+=p&-p) t[p] = A(t[p], v);
    }

    int query(int p){
        int ret = 0;
        for(;p;p-=p&-p) ret = A(ret, t[p]);
        return ret;
    }
} t;

int query(int u, int v){
    int ret = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ret = A(ret, S(t.query(seg[u]), t.query(seg[top[u]] - 1)));
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    ret = A(ret, S(t.query(seg[u]), t.query(seg[v] - 1)));
    return ret;
}

struct magic {
    int x, z;
    magic(int x = 0) : x(max(x, 1)), z(!x) {}
    magic(int x, int z) : x(x), z(z) {}
    magic operator*(int t) const { return t ? magic(M(x, t), z) : magic(x, z + 1); }
    magic operator/(int t) const { return t ? magic(M(x, I(t)), z) : magic(x, z - 1); }
    int operator()() const { return z ? 0 : x; }
} f[N];

void dp1(int u){
    f[u] = magic(1);
    for(int v : g[u]) dp1(v), f[u] = f[u] * A(f[v](), 1);
    t.update(seg[u], f[u]());
}

vector<pair<int,int>> qry[N];
int ans[N];

void dp2(int u){
    for(auto [v, id] : qry[u]) ans[id] = query(u, v);
    for(int v : g[u]){
        magic fv = f[v], fu = f[u];
        f[u] = f[u] / A(fv(), 1);
        f[v] = f[v] * A(f[u](), 1);
        t.update(seg[v], S(f[v](), fv())), t.update(seg[u],S(f[u](), fu()));
        dp2(v);
        t.update(seg[v], S(fv(), f[v]())), t.update(seg[u], S(fu(), f[u]()));
        f[u] = fu, f[v] = fv;
    }
}

void solve(){
    cin >> n >> q;
    for(int i=2;i<=n;i++) cin >> fa[i], g[fa[i]].push_back(i);
    top[1] = 1, dfs1(1), dfs2(1), dp1(1);
    for(int i=1,u,v;i<=q;i++){
        cin >> u >> v;
        if(dep[u] > dep[v]) swap(u, v);
        qry[u].emplace_back(v, i);
    }
    dp2(1);
    for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}

void clear(){
    seg[0] = 0;
    for(int i=1;i<=n;i++) g[i].clear(), son[i] = t.t[i] = 0, qry[i].clear();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan