随机游走问题(赌徒破产问题）

奶龙和噜噜的糖豆

题意
现在有一颗以 $1$ 为根的树，奶龙先选择一个叶子作为 $a$ ，噜噜再选择一个叶子作为 $b$ ，噜噜从 1 出发，先走到 $a$ 点的话，奶龙赢，否则奶龙输，奶龙想要自己赢，噜噜不想要奶龙赢，双方都采取最优策略，计算奶龙赢得概率

题解
如果糖豆走到既没有 $a$ ，也没有 $b$ 的节点，那么糖豆一定会在某个节点处往回走，所以只需要计算在既可以走到 $a$ ，又可以走到 $b$ 的时候，这一条路径上的概率，假设我现在在 $x$ 点，距离 $a$ 点为 $dist(x,a)$ ，距离 $b$ 点为 $dist(x,b)$ ，所以此时奶龙获胜的概率为： $dist(x,b)/dist(a,b)$

此时糖豆的出发点在 1, 假设接下来糖豆会走到 $(a,b)$ 路径的某点 $x$ 上
那么：
$dist(1,a)=dist(1,x)+dist(x,a)$
$dist(a,b)=dist(x,a)+dist(x,b)$
$dist(1,b)=dist(1,x)+dist(x,b)$
其中的 $dist(a,b)$ 是已知的，所以我们只需要求出 $dist(x,b)$
可得：
$dist(x,b)=(dist(a,b)+dist(1,b)-dist(1,a))/2$
所以只需要枚举 $a,b$ 两个点，计算就可以求出答案，同时需要维护当前最小的答案的分数用于比较

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl "\n"
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define pii pair<int,int>
//#define lc p<<1
//#define rc (p<<1) + 1
const int N = 2e5 + 10;
const int M = 5e5 + 10;
const int INF = 1e18;
int mod = 998244353;
 
int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = a * a % mod;
        b >>= 1;
    } 
    return res % mod;
}
 
int mn(int x){
    return qpow(x, mod - 2);
}
 
vi G[5201];
//需要 1 到 a 的距离，1 到 b 的距离，a 到 b 的距离，a,b就是两个lcm相加就好了
vii dis(5201, vi(5201));
void dfs(int u, int v, int fa){ //我已知 dis[u][v], v 是 fa 的儿子,其实就是找从 u 出发到每个点的最短距离
    for(auto k : G[v]){
        if(k == fa) continue;
        dis[u][k] = dis[u][v] + 1;
        dfs(u, k, v);
    }
    return;
}
 
void solve(){
    int n; cin >> n;
    vi cnt(n + 1);
    rep(i, 1, n - 1){
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        cnt[x] ++;
        cnt[y] ++;
    }
    rep(i, 1, n){
        //没个节点从它的儿子开始搜
        for(auto v : G[i]){
            dis[i][v] = 1;
            dfs(i, v, i);
        }
    }
 
    int fzz = 0, fmm = 0; //记录最大的概率的分子分母
    rep(i, 2, n){ 
        if(cnt[i] > 1) continue;
        int fz = 0, fm = 0;
        rep(j, 2, n){
            if(i == j) continue;
            if(cnt[j] > 1) continue;
            int t_fz = dis[i][j] + dis[1][j] - dis[1][i];
            int t_fm = 2 * dis[i][j];
            //cout << t_fz << " " << t_fm << endl;
            if(fz == 0 && fm == 0 && t_fz != t_fm){
                fz = t_fz; fm = t_fm;
            }else if(t_fz * fm < t_fm * fz && t_fz != t_fm){
                fz = t_fz;
                fm = t_fm;
            }
        }
        if(fzz == 0 && fmm == 0 && fz != fm){
            fzz = fz; fmm = fm;
        }else if(fz * fmm > fm * fzz && fz != fm){
                fzz = fz;
                fmm = fm;
            }
    }
    //cout << fz << " " << fm << endl;
    cout << fzz * mn(fmm) % mod << endl;
    rep(i, 1, n){
        G[i].clear();
        rep(j, 1, n){
            dis[i][j] = 0;
        }
    }
    return;
}   
 
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--) solve();
    return 0;
}