Coin
假设 \(1 \leqslant n \leqslant 100\)，可以想到去做一个矩阵乘法，记录一下每个位置到其他位置的概率。
尝试算一下概率，可以发现每个位置到除了它以外的每一个位置的概率都是 \(\frac{1}{2 \times (n - 1)}\)，停留在原地的概率为 \(\frac{1}{2}\)。
但是可以发现，除了最初他在的位置，其他位置的情况都是相同的。
那么就可以把矩阵从 \(n \times n\) 转成 \(2 \times 2\)。
推导一下，我的矩阵长成这样：\(\begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2 \times (n-1)} & \frac{n - 2}{2 \times (n-1)}+\frac{1}{2} \end{bmatrix}\)
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mod = 998244353, MATsize = 5;
struct matrix {
int a[MATsize][MATsize], n, m;
void Clear (int x, int y, int f) {
n = x, m = y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = f;
}
void Unit (int x, int y) {
Clear(x, y, 0);
for (int i = 1; i <= n; i++)
a[i][i] = 1;
}
matrix operator + (matrix y) {
matrix z;
z.n = n, z.m = m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
z.a[i][j] = a[i][j] + y.a[i][j];
return z;
}
matrix operator * (matrix y) {
matrix z;
z.n = n, z.m = y.m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= y.m; j++) {
z.a[i][j] = 0;
for (int k = 1; k <= m; k++)
z.a[i][j] = (z.a[i][j] + 1ll * a[i][k] * y.a[k][j] % mod) % mod;
}
return z;
}
} ;
matrix MATqmod (matrix x, ll y) {
matrix sum;
sum.Unit(x.n, x.m);
while (y) sum = (y & 1 ? sum * x : sum), x = x * x, y >>= 1;
return sum;
}
int qmod (int x, int y) {
int ret = 1;
while (y) ret = (y & 1 ? 1ll * ret * x % mod : ret), x = 1ll * x * x % mod, y >>= 1;
return ret;
}
ll n, k, x;
matrix a, b;
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
cin >> n >> x >> k;
a.Clear(1, 2, 0), a.a[1][1] = 1;
b.Clear(2, 2, 0), b.a[1][1] = qmod(2, mod - 2), b.a[1][2] = qmod(2, mod - 2), b.a[2][1] = 1ll * qmod(2, mod - 2) * qmod((n - 1) % mod, mod - 2) % mod, b.a[2][2] = ((n - 2) % mod * qmod((2 * n - 2) % mod, mod - 2) + qmod(2, mod - 2)) % mod;
a = a * MATqmod(b, k);
/*a = a * b;
cout << a.a[1][1] << ' ' << a.a[1][2] << '\n';
a = a * b;
cout << a.a[1][1] << ' ' << a.a[1][2] << '\n';*/
//assert((a.a[1][1] + a.a[1][2]) % mod == 1);
cout << (x % mod * a.a[1][1] + ll((_1 * n * (n + 1) / 2 - x) % mod) * a.a[1][2] % mod * qmod((n - 1) % mod, mod - 2)) % mod;
return 0;
}
Iwanna
结论：答案就是所有边的边权总和减去以 s 为根时 t 的子树范围内的边权之和。证明如下。
预处理后做个 lca，分类讨论一下即可。
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (const string s) {
freopen(string(s + ".in").c_str(), "r", stdin);
freopen(string(s + ".out").c_str(), "w", stdout);
}
const int N = 5e5 + 10, mod = 998244353;
int n, q, sum[N], fa[N][20], dep[N], x, y, fa_[N];
vector<pair<int, int>> g[N];
void dfs (int x) {
dep[x]++;
for (int i = 1; i <= 18; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (auto [i, j] : g[x])
if (i != fa[x][0])
fa[i][0] = x, fa_[i] = j, dep[i] = dep[x], dfs(i), sum[x] = (0ll + sum[x] + sum[i] + j) % mod;
}
int lca (int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 18; i >= 0; i--)
if ((dep[x] - dep[y]) >> i & 1)
x = fa[x][i];
if (x == y) return x;
for (int i = 18; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
cin >> n >> q;
for (int i = 1, x, y, z; i < n; i++)
cin >> x >> y >> z, g[x].push_back({y, z}), g[y].push_back({x, z});
dfs(1);
while (q--) {
cin >> x >> y;
if (x == y) {
cout << "0\n";
continue;
}
if (lca(x, y) == y) {
int z = x;
for (int i = 18; i >= 0; i--)
if ((dep[x] - dep[y] - 1) >> i & 1)
z = fa[z][i];
cout << (sum[z] + fa_[z]) % mod;
} else {
cout << (sum[1] - sum[y] + mod) % mod;
}
cout << '\n';
}
return 0;
}