小红的树上移动（牛客周赛50）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=1e6+10;
vector<ll>e[N];
ll md=0;
ll qpow2(ll a,ll b,ll p){
    ll base=a;
    ll res=1;
    while(b){
            if(b&1)res=(res*base)%p;
            base=(base*base)%p;
            b>>=1;
    }
    return res;
}

ll inv(ll a,ll b){
    return (a*qpow2(b,mod-2,mod))%mod;
}
ll a[N],b[N];
void dfs(ll x,ll fa,ll deep){
    a[deep]++;
    if(e[x].size()==1&&x!=1){//子节点
        b[deep]++;
        md=max(md,deep);
        return;
    }
    for(auto i:e[x]){
        if(i==fa)continue;
        dfs(i,x,deep+1);
    }
}
int main(){
    ll n;cin>>n;
    for(int i=1;i<n;i++){
        ll q,w;cin>>q>>w;
        e[q].push_back(w);
        e[w].push_back(q);
    }
    dfs(1,-1,0);
    ll sum=0,ff=1;
    for(int i=1;i<=md;i++){
        sum+=ff;
        ff*=inv(a[i]-b[i],a[i]);
        ff%=mod;
        sum%=mod;
    }
    cout<<sum<<endl;
}