NOIP2023模拟9联测30 D. 金牌

NOIP2023模拟9联测30 D. 金牌

题目大意

有一棵 \(n\) 个节点的树。

假设一条路径的长度为 \(d\) ，那么这条路径的价值为 \(2^d\)

现在有 \(k\) 个询问，每次给定两个整数 \(x , y\) ，询问所有同时通过顶点 \(x\) 和 \(y\) 的简单路径的价值之和 (\(\mod 998244353\))

思路

考虑维护两个数组 \(sum_x , vs_x\) ，分别表示以 \(x\) 为根的子树中的所有点到 \(x\) 距离的二次幂之和、不在 \(x\) 的子树的所有点到 \(x\) 距离的二次幂之和。用一个换根 \(dp\) 就可以了

设询问为 \(x , y\)，他们的距离为 \(d\) ，

设 \(A\) 为在图中与 \(x\) 的路径不经过 \(x\to y\) 这条路径上的点的点集

设 \(B\) 为在图中与 \(y\) 的路径不经过 \(x\to y\) 这条路径上的点的点集

答案就是

\[2^d * (\sum_{u\in A} 2^{dis(u , x)}) * (\sum_{v\in B} 2^{dis(v , y)}) \]

如果 \(lca(x , y) \neq x \and lca (x , y) \neq y\)

那么答案为 \(2^d * sum_x * sum_y\)
否则

设 \(y \neq lca\) ，\(t\) 为 \(x\to y\) 路径中离 \(x\) 最近的点

答案为 \(2^d * sum_y *(vs_x +sum_x - 2 *sum_t)\)

用 \(tarjan\) 求 \(lca\) 每次在 \(tarjan\) 中维护一下现在在走 \(x\) 的那个儿子，就可以搞到上面的 \(t\)

code

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N =1e6 + 5;
const LL mod = 998244353;
int hd[N] , cnt , q[N] , cnt2 , dep[N] , n , lca[N] , to[N] , fa[N] , p[N] , st[N] , flg[N] , xx[N] , yy[N] , res[N];
LL sum[N] , vs[N] , mi[N];
struct node {
    int to , nt , id;
} query[N << 1];
struct E {
    int to , nt;
} e[N << 1];
inline int read () {
    int val = 0;
    char ch = getchar ();
    while (ch < '0' || ch > '9') ch = getchar ();
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        ch = getchar ();
    }
    return val;
}
inline void write (LL x) {
    if (x >= 10) write (x / 10);
    putchar (x % 10 + '0');
}
inline void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; } 
inline void add2 (int x , int y , int i) { query[++cnt2].to = y , query[cnt2].nt = q[x] , q[x] = cnt2 , query[cnt2].id = i; }
inline void dfs1 (int x) {
    int y;
    sum[x] = 1;
    dep[x] = dep[fa[x]] + 1;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        fa[y] = x;
        dfs1 (y);
        sum[x] = (sum[x] + sum[y] * 2) % mod;
    }
}
inline int find (int x) {
    if (x == p[x]) return x;
    else return p[x] = find (p[x]);
}
inline void dfs2 (int x) {
    int y;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        vs[y] = (vs[x] + sum[x] - 2 * sum[y] + 2 * mod) * 2 % mod;
        dfs2 (y);
    }
}
inline void dfs3 (int x) {
    st[x] = 2;
    int y , Lca , id;
    for (int i = q[x] ; i ; i = query[i].nt) {
        y = query[i].to;
        if (!st[y]) continue;
        Lca = find (y);
        id = query[i].id;
        lca[id] = Lca;
        res[id] = dep[x] + dep[y] - dep[Lca] * 2;
        to[id] = flg[Lca];
    }
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        flg[x] = y;
        dfs3 (y);
        p[y] = x;
    } 
    st[x] = 1;
}
int main () {
    freopen ("d.in" , "r" , stdin);
    freopen ("d.out" , "w" , stdout);
    int u , v;
    // int ttt=clock();
    n = read ();
    mi[0] = 1;
    for (int i = 1 ; i <= n ; i ++) mi[i] = mi[i - 1] * 2 % mod;
    for (int i = 1 ; i <= n ; i ++) p[i] = i;
    for (int i = 1 ; i <= n - 1 ; i ++) {
        u = read () , v = read ();
        add (u , v) , add (v , u);
    }
    int q = read ();
    for (  int i = 1 ; i <= q ; i ++) {
        xx[i] = read () , yy[i] = read ();
        add2 (xx[i] , yy[i] , i);
        add2 (yy[i] , xx[i] , i);
    }
    dep[1] = 1;
    dfs1 (1);
    dfs2 (1);
    dfs3 (1);
    // for (int i = 1 ; i <= n ; i ++) cout << sum[i] << "\n";
    // return 0;
    for (int i = 1; i <= q ; i ++) {
        u = xx[i] , v = yy[i];
        if (lca[i] != u && lca[i] != v) {
            write (mi[res[i]]* sum[u] % mod * sum[v] % mod);
        }
        else {
            if (u == lca[i]) swap (u , v); 
            write (mi[res[i]] * sum[u] % mod * (vs[v] + sum[v] - 2 * sum[to[i]] + 2 * mod) % mod);
        }
        putchar('\n');
    }
    // cout<<(clock()-ttt)<<endl;
    return 0;
}