Gym102174L 旅行的意义（期望dp）

因为是dag，所以常规做法就是dfs，从出度为0的点不断返回

我们设计f[i]，表示从i开始到终点的期望天数

刚开始到i需要一天，在i需要游玩一天，再游玩一天有（du[i]+1）的可能性，这是初始化的情况

之后就是从他的后继节点更新过来。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=2e5+10;
const ll mod=998244353;
int h[N],ne[N],e[N],idx;
int du[N];
ll f[N];
int n,m;
int st[N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
    st[u]=1;
    f[u]=(2+qpow(du[u]+1,mod-2))%mod;
    if(u==1){
        f[u]=(f[u]-1+mod)%mod;
    }
    int i;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j])
            dfs(j);
        f[u]=(f[u]+f[j]*qpow(du[u],mod-2))%mod;
    }
}
int main(){
    //ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        idx=0;
        int i,j;
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++){
            h[i]=-1;
            du[i]=0;
            f[i]=0;
            st[i]=0;
        }
        for(i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
            du[a]++;
        }
        dfs(1);
        printf("%lld
",f[1]%mod);
    }
}