P6154 wandering (memory search

Add link description

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+9, mod=998244353;
int tot[N],sum[N];
vector<int>v[N];
int dfs(int u){
    
    if(tot[u])return tot[u];
    tot[u]=1;
    for(auto it:v[u]){
    
        int p=dfs(it);
        tot[u]+=p;// Number of nodes after adding 
        sum[u]+=p+sum[it];// Add the number of subsequent nodes and the distance from the current node to the subsequent nodes 
        tot[u]%=mod;
        sum[u]%=mod;
    }
    return tot[u];
}
int q_pow(int a,int b){
    
    int ans=1;
    while(b){
    
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
signed main(){
    
    int n,m;
    cin>>n>>m;
    while(m--){
    
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
    
        dfs(i);
    }
    int a=0,b=0;
    for(int i=1;i<=n;i++){
    
        a+=sum[i];
        b+=tot[i];
        a%=mod;
        b%=mod;
    }
    // cout<<a<<" "<<b<<"\n";
    cout<<a*q_pow(b,mod-2)%mod;
    return 0;
}