The 14-th BIT Campus Programming Contest L. 旅行的意义

旅行的意义

参考于：xls tql

d[i]表示以i为起点的期望天数，

对于节点u，首先需要在u玩一天，第二天我可以有1 / (son + 1)概率去u的某一个子节点，也有1 / (son + 1)概率待在u，d[u] = 1，d[u] = d[u] + （d[vi] + 1）* 1 / (son + 1) + 1 / (son + 1)，坐车需要一天所以是d[vi] + 1，如果第二天我还在u，那么第三天我必须要走了，去u的某一个子节点，概率为1 / (son + 1) * 1 / son ,d[u] = d[u] +  1 / (son + 1) * 1 / son * (d[vi] + 1) ， 

所以 d[u] = d[u] + （d[vi] + 1）* 1 / (son + 1)  +   1 / (son + 1) * 1 / son * (d[vi] + 1) + 1 / (son + 1)

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+100;
typedef long long ll;
#define mod 998244353
int t;
int n,m;
vector<int> G[M];
int vis[M];
ll d[M];
ll p[M];

void init(){
	for(int i = 0; i <= n; i++){
		G[i].clear();
	}
	memset(vis, 0, sizeof(int)*(n+1));
}

ll qpow(ll a, int x){
	ll res=1;
	while(x){
		if(x & 1) res = res * a % mod;
		a = a * a % mod;
		x /= 2;
	}
	return res;
}

void dfs(int u){
	int v;
	d[u]=1;
	int son=G[u].size();
	for(int i = 0; i < son; i++){
		v = G[u][i];
		if(!vis[v]){
			vis[v] = 1;
			dfs(v);
		}
		d[u] = d[u] + p[1 + son] * (d[v] + 1) % mod + p[1 + son] * p[son] % mod * (d[v] + 1) %mod;
		d[u] %= mod;
	}
	d[u]=(d[u] + p[1 + son]) % mod;
}
int main(){
	scanf("%d", &t);
	p[1] = 1ll;
	for(int i = 2; i <= 100000; i++){
		p[i] = qpow(1ll * i, mod - 2);
	}
	while(t--){
		scanf("%d%d", &n, &m);
		init();
		int u, v;
		for(int i = 0; i < m; i++){
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
		}
		vis[1]=1;
		dfs(1);
		printf("%lld\n",d[1]);
	}
	return 0;
}