一道推式子题。
首先列出柿子,(ans=sumlimits_{T_2}|T_1cap T_2|·2^{T_1cap T_2})
这个东西没法直接处理,不过注意到有一个柿子 (f(S)=sumlimits_{Tsubseteq S}sumlimits_{T'subseteq T}(-1)^{T-T'}f(T')),证明可考虑计算每个 (T') 的贡献,由于 (T'subseteq Tsubseteq S),(T) 必然是 (T') 与 (S-T') 的某个子集的并,于是我们尝试枚举这个子集的大小,可得 (T') 在对这个柿子结果的贡献为 (f(T')sumlimits_{i=0}^{|S-T'|}dbinom{|S-T'|}{i}(-1)^i=0^{|S-T'|}·f(T')),因此只有当 (T'=S) 时对结果产生 (f(T')) 的贡献,其余 (T') 的贡献均为 (0),得证。
考虑将这个柿子应用于这道题上,记 (f(S)=|S|·2^{|S|}),那么
推到这里,聪明的你一定已经发现,(sumlimits_{Sin T_2}1) 就是包含 (S) 当中边的生成树个数,于是题目要求的就是对于所有边集 (S),包含 (S) 的生成树个数乘上 (S) 的大小之和,而又根据我们在这里推得的结论:包含 (S) 的生成树个数就是 (n^{r-2}prodlimits_{i=1}^ra_i),其中 (r) 为 (S) 中的边形成的连通块个数,(a_1,a_2,cdots,a_r) 为这 (r) 个连通块的大小。
于是答案可进一步可进一步写成 (2sumlimits_{Sin T_1}|S|n^{r-2}prodlimits_{i=1}^ra_i=dfrac{2}{n^2}sumlimits_{Sin T_1}|S|prodlimits_{i=1}^rna_i),此时这玩意儿的组合意义就异常明显了:选择一个边集将这棵树分成若干个连通块,再从每个连通块中选择一个点,产生 (n) 的乘积贡献,最后从选定的边集中选择一条边,球所有选法的贡献之和。
这样就可以 DP 了,(dp_{u,0/1,0/1}) 表示确定了以 (u) 为根的子树内连通块的划分情况,(u) 所在的连通块是否选择了点,(u) 子树内是否有边被选择的方案数,树上背包转移即可。
时间复杂度 (mathcal O(16n))(虽然我深知这个写法非常不规范/cy/cy)
const int MAXN=2e6;
const int MOD=998244353;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int dp[MAXN+5][2][2],tmp[2][2];
void dfs(int x,int f){
dp[x][0][0]=1;dp[x][1][0]=n;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;dfs(y,x);fill0(tmp);
for(int p=0;p<2;p++) for(int q=0;q<2;q++)//not seperate and not choose
for(int u=0;u+p<2;u++) for(int v=0;v+q<2;v++)
tmp[u+p][v+q]=(tmp[u+p][v+q]+1ll*dp[x][p][q]*dp[y][u][v])%MOD;
for(int p=0;p<2;p++) for(int u=0;u+p<2;u++) tmp[u+p][1]=(tmp[u+p][1]+1ll*dp[x][p][0]*dp[y][u][0])%MOD;//not seperate and choose
for(int p=0;p<2;p++) for(int q=0;q<2;q++) for(int v=0;v+q<2;v++)//seperate
tmp[p][v+q]=(tmp[p][v+q]+1ll*dp[x][p][q]*dp[y][1][v])%MOD;
for(int p=0;p<2;p++) for(int q=0;q<2;q++) dp[x][p][q]=tmp[p][q];
} //printf("%d %d %d %d %d
",x,dp[x][0][0],dp[x][0][1],dp[x][1][0],dp[x][1][1]);
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
dfs(1,0);printf("%d
",2ll*qpow(n,MOD-3)*dp[1][1][1]%MOD);
return 0;
}