C++14(g++5.4) 解法, 执行用时: 110ms, 内存消耗: 15704K, 提交时间: 2019-03-13 20:58:02

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,mod=998244353;
ll ksm(ll x,int y)
{
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}
ll d[maxn],inv[maxn],ans,sum;
int sz[maxn],n;
vector<int>G[maxn];
void mul(ll& x,ll y)
{
	x=x*y%mod;
}
void add(ll& x,ll y)
{
	x=(x+y)%mod;
}
void dfs(int u,int fa)
{
	sz[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		mul(sum,inv[sz[v]]);
	}
}
void dfs2(int u,int fa,ll res)
{
	add(ans,res);
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa)continue;
		dfs2(v,u,res*sz[v]%mod*inv[n-sz[v]]%mod);
	}
}
int main()
{
	int u,v;
	scanf("%d",&n);
	sum=inv[0]=1;
	for(int i=1;i<=n;i++)
	mul(sum,i),inv[i]=ksm(i,mod-2);
	mul(sum,inv[n]);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	dfs2(1,0,sum);
	printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 123ms, 内存消耗: 18148K, 提交时间: 2019-03-08 19:49:10

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int _=1e5+5,yl=998244353;
ll f[_],deg[_],siz[_],inv[_],mul[_],n,ans;
vector<int>e[_];
ll POW(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)res=res*x%yl;
		x=x*x%yl;y>>=1;
	}
	return res;
}
void dfs(int fa,int u){
	f[u]=1;
	for(int v:e[u]){
		if(v==fa)continue;dfs(u,v);siz[u]+=siz[v];
		f[u]=f[u]*f[v]%yl*siz[v]%yl;
	}
	siz[u]++;
}
void Dfs(int fa,int u,ll x){
	ans+=mul[n-1]*POW(f[u]*x%yl,yl-2)%yl;
	for(int v:e[u]){
		if(v==fa)continue;
		Dfs(u,v,f[u]*x%yl*POW(f[v]*siz[v]%yl,yl-2)%yl*(n-siz[v])%yl);
	}
}
int main(){
	ios::sync_with_stdio(false);
	inv[0]=inv[1]=mul[0]=1;cin>>n;
	for(int i=2;i<=n;++i)inv[i]=(yl-yl/i)*inv[yl%i]%yl;
	for(int i=1;i<=n;++i)mul[i]=mul[i-1]*i%yl,inv[i]=inv[i]*inv[i-1]%yl;
	for(int i=1;i<n;++i){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(0,1);Dfs(0,1,1);cout<<ans%yl<<endl;
	return 0;
}