題面：

從 \(1\) 出發(fā)，求期望 dfn 序。

\(1\) 點很特殊，先固定 \(1\) 點，發(fā)現(xiàn)去除 \(1\) 后是森林，而 \(1\) 把他們都連起來了。

由于 \(1\) 開始走，所以相當(dāng)于 \(1\) 連的邊欽定了很多樹的很多根。

先固定一棵樹的一個根 \(rt\)，思考這時 \(x\) 點的期望 dfn 序會被三種點貢獻：

• \(rt→x\) 每個點貢獻 \(1\)。
• \(x\) 子樹內(nèi)每個點貢獻 \(0\)。
• 其他節(jié)點貢獻 \(\frac{1}{2}\)。
  有點反直覺證一下：
  假設(shè) \(v\) 為其他節(jié)點，\(x\) 與 \(v\) 相對順序只有兩種，手玩一下就知道了。

根之間是平等的，所以把所有根跑一遍所有節(jié)點的期望 dfn 序，每個節(jié)點可以把加和除以當(dāng)前樹根的總數(shù)。

\(dfn_x=\frac{\sum_{rt}dis(x,rt)+siz_{rt}-(siz_x-1)+1}{2×cnt}\)
（這里的 \(cnt\) 指 \(x\) 所在樹樹根個數(shù)）
可以換根 DP。

此時是不考慮樹之間影響時每個節(jié)點的期望 dfn 序。

考慮樹之間影響怎么辦？這時可以看出來我們進一個樹就必須跑完這個樹，從樹遍歷的相對順序來看，顯然 \(T\) 對 \(S\) 造成貢獻是 \(\frac{cnt_Tsiz_T}{cnt_S+cnt_T}\)（這里的 \(cnt_T\) 指 \(T\) 樹根個數(shù)）。這題數(shù)據(jù)很水直接枚舉樹對就能過，但是實際上我們還有最后一步：
把 \(cnt_T\) 相同的樹合并成一塊，合并完顯然最多 \(O(\sqrt n)\) 種，在兩兩塊之間計算貢獻，可以發(fā)現(xiàn)只需要對每個塊記錄 \(\sum siz\) 就能做到。

按上面模擬就好了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=5e5+7,mo=998244353;
int n,m,gj[QAQ];
vector<int> dian[QAQ];
int siz[QAQ],cntrt[QAQ],dis[QAQ];
int f[QAQ];
int find(int x) {return x==f[x]?f[x]:f[x]=find(f[x]);}
void dfs1(int x,int ba)
{
	cntrt[x]=gj[x];
	siz[x]=1;
	dis[x]=0;
	for(int v:dian[x])
	{
		if(v==ba||v==1) continue;
		dfs1(v,x);
		f[find(v)]=find(x);
		dis[x]+=dis[v]+cntrt[v];
		siz[x]+=siz[v];
		cntrt[x]+=cntrt[v];
	}
}
int ksm(int x,int k)
{
	int da=1;
	for(;k;k>>=1,x=x*x%mo) if(k&1) da=da*x%mo;
	return da;
}
int ans[QAQ],g[QAQ];
void dfs2(int x,int ba)
{
	ans[x]=dis[x]+g[x]+
		siz[find(x)]*cntrt[find(x)]
		-(cntrt[find(x)]-cntrt[x])*(siz[x]-1)
		-gj[x]*(siz[find(x)]-1)+
		cntrt[find(x)];
	ans[x]%=mo;
	for(int v:dian[x])
	{
		if(v==ba||v==1) continue;
		ans[x]-=cntrt[v]*(siz[find(x)]-siz[v]-1);
		ans[x]%=mo;
	}
	ans[x]=ans[x]*ksm(2,mo-2)%mo*ksm(cntrt[find(x)],mo-2)%mo;
	for(int v:dian[x])
	{
		if(v==ba||v==1) continue;
		g[v]=g[x]+cntrt[find(x)]-cntrt[v]+dis[x]-(dis[v]+cntrt[v]);
		dfs2(v,x);
	}
}
vector<int> cun,ccx;
int cf[QAQ],tong[QAQ];
signed main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
		cin>>u>>v,dian[u].push_back(v),dian[v].push_back(u);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int v:dian[1]) gj[v]=1;
	for(int v:dian[1]) if(v==find(v)) dfs1(v,1);
	for(int v:dian[1]) if(v==find(v)) dfs2(v,1),cun.push_back(v);
	for(int x:cun)
	{
		if(!tong[cntrt[x]]) ccx.push_back(cntrt[x]);
		tong[cntrt[x]]+=siz[x];
	}
	for(int x:ccx) for(int v:ccx) cf[v]=(cf[v]+tong[x]*x%mo*ksm(x+v,mo-2)%mo);
	cout<<1<<' ';
	for(int i=2;i<=n;i++) if(ans[i]) cout<<(ans[i]+cf[cntrt[find(i)]]-siz[find(i)]*ksm(2,mo-2)%mo+1+mo)%mo<<" "; else cout<<0<<" ";
	return 0;
}