P15076 [ICPC 2024 Chengdu R] Disrupting Communications 题解

:::info[Description] Link. :::

:::infoSolution 简单题。考虑设 $f_i$ 表示只选择 $i$ 子树内的结点且必选 $i$ 的合法连通块数量， $g_i$ 表示确定选 $i$ 位置的合法连通块数量。 $f_i$ 是容易算的， $g_i$ 可以直接换根 dp 然后为了避免出现除以 $0$ 的情况上前后缀合并即可。

然后考虑算答案。为了不算重，把 LCA 位置按 $g_i$ 来算，非 LCA 位置按照 $f_i$ 来算然后直接求和就可以得到答案。

时间复杂度为 $O((n+Q)\log n)$ ，可以通过该题。 :::

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

vector<int> adj[N];
int st[N][20], dep[N], pre[N], f[N], g[N], h[N];
inline void dfs(int u, int fa) {
    f[u] = 1, dep[u] = dep[fa] + 1, st[u][0] = fa;
    for (int &v : adj[u]) if (v != fa)
        dfs(v, u), f[u] = f[u] * (f[v] + 1) % mod;
}
inline void dfs2(int u, int fa) {
    pre[u] = (pre[fa] + f[u]) % mod;
    if (!fa) {
        g[u] = f[u];
        int pre = 1, suf = 1;
        for (int &v : adj[u]) if (v != fa){ 
            h[v] = h[v] * pre % mod;    
            pre = pre * (f[v] + 1) % mod;
        }
        for (int &v : adj[u] | views::reverse) if (v != fa) {
            h[v] = h[v] * suf % mod;
            suf = suf * (f[v] + 1) % mod;
        }
    } else {
        g[u] = f[u] * (h[u] + 1) % mod;
        int pre = (h[u] + 1) % mod, suf = 1;
        for (int &v : adj[u]) if (v != fa){ 
            h[v] = h[v] * pre % mod;
            pre = pre * (f[v] + 1) % mod;
        }
        for (int &v : adj[u] | views::reverse) if (v != fa) {
            h[v] = h[v] * suf % mod;
            suf = suf * (f[v] + 1) % mod;
        }
    } for (int &v : adj[u]) if (v != fa) dfs2(v, u);
}
inline int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 19; ~i; --i)
        if (dep[a] - dep[b] >> i & 1) a = st[a][i];
    if (a == b) return a;
    for (int i = 19; ~i; --i)
        if (st[a][i] != st[b][i]) a = st[a][i], b = st[b][i];
    return st[a][0];
}
inline int dist(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) h[i] = 1, adj[i].clear();
    for (int i = 2; i <= n; ++i) {
        int x; cin >> x;
        adj[i].emplace_back(x), adj[x].emplace_back(i);
    } dfs(1, 0), dfs2(1, 0);
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j <= n; ++j) st[j][i] = st[st[j][i - 1]][i - 1];
    while (q--) {
        int u, v; cin >> u >> v;
        int L = lca(u, v);
        cout << (pre[u] + pre[v] - 2 * pre[L] % mod + mod + g[L]) % mod << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：青

鲜活指数：5

隐藏／恢复文章

随机文章