思路

对于每个节点来说，对答案的期望贡献都是其深度的倒数。因此，我们只要将每个点贡献累加就能得到最终期望。 用快速幂求每个贡献($\frac{1}{dep[i]}\backslash frac\{1\}\{dep[i]\}$)的逆元，再相加就是最终答案。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=998244353;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

int fpow(int a,int p){
	int res=1;
	while(p){
		if(p&1) res=res*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return res;
}

vector<int>G[N];
int sz[N],fa[N],dep[N];
void dfs(int x){
	sz[x]=1;
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==fa[x]) continue;
		fa[to]=x;
		dep[to]=dep[x]+1;
		dfs(to);
		sz[x]+=sz[to];
	}
}

int n,u,v,res;
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[1]=1;
	dfs(1);
	for(int i=1;i<=n;i++){
		res+=fpow(dep[i],mod-2);
		res%=mod;
	}
	cout<<res<<"\n";
	return 0;
}