NOIP2023模拟9联测30 D. 金牌

本文主要是介绍NOIP2023模拟9联测30 D. 金牌，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NOIP2023模拟9联测30 D. 金牌

文章目录

NOIP2023模拟9联测30 D. 金牌
- 题目大意
- 思路
- code

题目大意

有一棵 $n$ 个节点的树。

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

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

思路

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

设询问为 $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)})$

如果 $KaTeX parse error: Undefined control sequence: \and at position 19: …(x , y) \neq x \̲a̲n̲d̲ ̲lca (x , y) \ne…$

那么答案为 $2^d * sum_x * sum_y$
否则

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

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

用 $t a r jan$ 求 $l c a$ 每次在 $t a r jan$ 中维护一下现在在走 $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;
}