C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 604K, 提交时间: 2022-09-09 21:11:58

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f)) 
#define uint unsigned int
using namespace std;
const int N = 107, mod = 998244353; 
int qpow(int x, int y = mod - 2) {
	int res = 1;
	for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
	return res;
}

int n, f[N][N], g[N][N], siz[N];
int cf[N], cg[N];
vi e[N];
void dfs(int x, int fa) {
	for(const int &v : e[x]) if(v != fa) {
		dfs(v, x);
	}
	f[x][1] = 1, f[x][0] = 1, g[x][0] = 1, siz[x] = 1;
	for(const int &v : e[x]) if(v != fa) {
		me(cf, 0), me(cg, 0);
		L(u, 0, siz[x]) {
			L(i, 0, siz[v]) {
				int A = qpow(4, siz[x] * siz[v] - u * i), tv;
				
				tv = (ll) f[x][u] * f[v][i] % mod * A % mod;
				(cf[0] += (ll) (qpow(4, u * i) - 1) * tv % mod) %= mod;
				if(u) (cf[u + i] += tv) %= mod;
				else (cf[0] += tv) %= mod;
				(cg[0] += (ll) (qpow(4, u * i) - 1) * tv % mod) %= mod;
				
				tv = ((ll) f[x][u] * g[v][i] % mod + (ll) g[x][u] * f[v][i] % mod) * A % mod;
				(cg[0] += (ll) (qpow(4, u * i) - 1) * tv % mod) %= mod;
				if(u) (cg[u + i] += tv) %= mod;
				else (cg[0] += tv) %= mod;
			}
		}
		swap(cf, f[x]), swap(cg, g[x]);
		siz[x] += siz[v];
	}
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	L(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfs(1, 0);
	int ns = 0;
//	L(i, 0, n) cout << f[1][i] << ' ';
//	cout << '\n';
	L(i, 0, n) (ns += g[1][i]) %= mod;
	cout << ns << '\n';
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 532K, 提交时间: 2022-10-15 21:44:49

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
const int N=105,M=20005,mod=998244353;
int qpow(int a,int k)
{
	int res=1;
	while(k)
	{
		if(k&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		k>>=1;
	}
	return res;
}
vector<int>g[N];
int pw[M],ipw[M];
int n;
int f[N][N],tmp[N];
int siz[N];
void dfs(int u,int fa)
{
	siz[u]=1;
	f[u][0]=f[u][1]=(mod+1)/2;
	for(int v:g[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		for(int i=0;i<=siz[u];++i)
		{
			for(int j=0;j<=siz[v];++j)
			{
				if(!i) tmp[0]=(tmp[0]+1ll*f[u][i]*f[v][j])%mod;
				else
				{
					tmp[i+j]=(tmp[i+j]+1ll*f[u][i]*f[v][j]%mod*ipw[2*i*j])%mod;
					tmp[0]=(tmp[0]+1ll*f[u][i]*f[v][j]%mod*(mod+1-ipw[2*i*j]))%mod;
				}
			}
		}
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];++i) f[u][i]=tmp[i],tmp[i]=0; 
	}	
}
int main()
{
	read(n);
	for(int i=1;i<n;++i)
	{
		int u,v;read(u),read(v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	pw[0]=1;
	for(int i=1;i<=n*n;++i)
		pw[i]=2ll*pw[i-1]%mod;
	ipw[n*n]=qpow(pw[n*n],mod-2);
	for(int i=n*n-1;i>=0;--i)
		ipw[i]=2ll*ipw[i+1]%mod;
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;++i) ans=(ans+f[i][0])%mod;
	ans=1ll*ans*pw[n*n]%mod;
	printf("%d\n",ans);
}