SDU Open 2023-F、树上随机游走
题目：https://codeforces.com/group/2altttv8oU/contest/477604/problem/F
题意：给定一棵 \(n\) 个点的无根树，在树上随机游走（即每次会从当前点等概率地走到一个相邻结点），\(q\) 次询问，每次问从 \(s\) 走到 \(t\) 的期望步数。
\(1\leq n,q\leq 2\times 10^5\)。
题解：
虽然不算难，但感觉是个很有意思的题。
首先要明确的一点是，从父亲走到儿子，和从儿子走到父亲是两种不同的情况，因此应该是先从 \(s\) 走到 \(LCA(s,t)\) ，再从 \(LCA(s,t)\) 走下去，这要分两段考虑。
设 \(f_x\) 表示从 \(x\) 走到父亲的期望步数，假设点 \(x\) 的度是 \(deg_x\) ，那么有\(p=1/deg_x\) 的概率走到每个相邻的点。考虑走一步之后，有 \(p\) 的概率直接走到父亲，以及剩下的情况等概率走到每个孩子，对于这些情况需要先从孩子走上来，再从 \(x\) 到父亲 ，即：
\[f_x=1+\sum_{v\in son_x}p\times (f_x+f_v)=1+(1-p) f_x+p\cdot \sum_{v\in son _x} f_v \]得到
\[f_x=\frac{1}{p}+\sum_{v\in son_x} f_v \]类似地考虑 \(g_x\) 表示从 \(x\) 的父亲走到 \(x\) 的期望步数，\(fa[x]\) 表示 \(x\) 的父亲，\(p=1/deg_{fa[x]}\) ，则从 \(fa[x]\) 出发，有 \(p\) 的概率走到\(fa[fa[x]]\)，此时需要再走到 \(fa[x]\) 需要期望 \(g_{fa[x]}\) 步，以及另外有概率走到 \(x\) 的兄弟结点，则
\[\begin{aligned} g_x&=1+ p(g_{fa[x]}+g_x)+\sum_{v\in son_{fa[x]},v\neq x}p(g_x+f_v)\\ &=1+(1-p)g_x+p\cdot g_{fa[x]}+g\cdot \sum_{v\in son_{fa[x]},v\neq x}f_v \end{aligned} \]化简得到
\[g_x=\frac{1}{p}+g_{fa[x]}+\sum_{v\in son_x,v\neq x}f_v \]两个dp都可以用 \(O(n)\) 的树dp完成。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=998244353;
void add(ll &x,ll y){x+=y;if(x>=MOD)x-=MOD;}
int n,q,fa[N],deg[N];
ll f[N],g[N];
vector<vector<int>> G;
namespace LCA{
int sz[N],fa[N],top[N],dep[N],son[N];
void dfs1(int x){
sz[x]=1;
for(auto to:G[x])if(to!=fa[x]){
dep[to]=dep[x]+1;
fa[to]=x;dfs1(to);
sz[x]+=sz[to];
if(sz[to]>sz[son[x]])son[x]=to;
}
}
void dfs2(int x,int t){
top[x]=t;
if(son[x])dfs2(son[x],t);
for(auto to:G[x])if(to!=fa[x]&&to!=son[x])dfs2(to,to);
}
int lca(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]])swap(a,b);
a=fa[top[a]];
}
if(dep[a]<dep[b])swap(a,b);
return b;
}
};
void dfs1(int x){
f[x]=deg[x];
for(auto to:G[x])if(to!=fa[x]){
fa[to]=x;
dfs1(to);
add(f[x],f[to]);
}
}
void dfs2(int x){
ll sum=0;
for(auto to:G[x])if(to!=fa[x])add(sum,f[to]);
for(auto to:G[x])if(to!=fa[x])
g[to]=(deg[x]+g[x]+sum-f[to]+MOD)%MOD;
}
int main(){
fastio;
cin>>n>>q;
G=vector<vector<int>>(n+1);
rep(i,1,n-1){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
deg[u]++;deg[v]++;
}
dfs1(1);dfs2(1);
rep(i,1,n)if(fa[i])add(f[i],f[fa[i]]),add(g[i],g[fa[i]]);
LCA::dfs1(1);LCA::dfs2(1,1);
rep(i,1,q){
int a,b;cin>>a>>b;
int L=LCA::lca(a,b);
ll ans=((f[a]-f[L]+MOD)%MOD+(g[b]-g[L]+MOD)%MOD)%MOD;
cout<<ans<<endl;
}
return 0;
}