LOJ

分析

感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。

我们还是套用
$$
f(S) = \sum_{T \subseteq S} \sum_{P \subseteq T} (-1)^{|T| - |P|} f(P)
$$
可以得到答案为
$$
\sum_{T_2} \sum_{S \subseteq T_1 \cap T_2} \sum_{T \subseteq S} (-1)^{|S| - |T|} |T| \cdot 2^{|T|}
$$
设 $g(S)$ 为包含 $S$ 中边的生成树个数，上式可以化为
$$
\begin{aligned}
& \sum_{S \subseteq T_1} \left(\sum_{T \subseteq S} (-1)^{|S| - |T|} \cdot |T| \cdot 2^{|T|}\right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \left(\sum_{T \subseteq S} (-2)^{|T|} \cdot |T|\right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \left(\sum_{i = 0}^{|S|} {|S| \choose i} (-2)^i \cdot i\right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \left(\sum_{i = 0}^{|S|} {|S| \choose i} {i \choose 1} (-2)^i \right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \cdot |S| \left(\sum_{i = 0}^{|S|} {|S| - 1 \choose i - 1} (-2)^i \right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \cdot (-2|S|) \left(\sum_{i = 1}^{|S| - 1} {|S| - 1 \choose i} (-2)^i \right) g(S) \\
= & \sum_{S \subseteq T_1} (-1)^{|S|} \cdot (-2|S|) \cdot (-1)^{|S| - 1} \cdot g(S) \\
= & 2 \sum_{S \subseteq T_1} |S| \cdot g(S) \\
\end{aligned}
$$
根据熟知结论有
$$
g(S) = n^{k - 2} \prod_{i = 1}^k a_i
$$
其中 $k$ 为连通块数，$a_i$ 为连通块大小。

代入上式中，上式化为
$$
\begin{aligned}
& 2 \sum_{S \subseteq T_1} |S| \cdot n^{k - 2} \prod_{i = 1}^k a_i\\
= & \frac{2}{n^2} \sum_{S \subseteq T_1} |S| \prod_{i = 1}^k na_i
\end{aligned}
$$
$\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。

考虑 DP。设 $f_{u, 0/1, 0/1}$ 表示以 $u$ 为根的子树、$u$ 所在连通块中是否已经选择了点、$u$ 子树中是否已经选择了边的贡献总和。转移类似树形背包，加入一个儿子时考虑这条边选或不选即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 2000000 + 10;
const int mod = 998244353;
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int n;
vector<int> E[N];

int f[N][2][2], g[2][2];
void dfs(int u, int fa) {
    f[u][0][0] = 1, f[u][1][0] = n;
    for (int v : E[u]) {
        if (v == fa) continue;
        dfs(v, u);
        memset(g, 0, sizeof(g));
        for (int x = 0; x <= 1; ++x)
            for (int y = 0; y <= 1; ++y)
                for (int p = 0; x + p <= 1; ++p)
                    for (int q = 0; y + q <= 1; ++q) {
                        g[x | p][y | q] = (g[x | p][y | q] + 1ll * f[u][x][y] * f[v][p][q]) % mod;
                        if (!(y | q)) g[x | p][1] = (g[x | p][1] + 1ll * f[u][x][0] * f[v][p][0]) % mod;
                    }
        for (int x = 0; x <= 1; ++x)
            for (int y = 0; y <= 1; ++y)
                for (int q = 0; y + q <= 1; ++q)
                    g[x][y | q] = (g[x][y | q] + 1ll * f[u][x][y] * f[v][1][q]) % mod;
        memcpy(f[u], g, sizeof(g));
    }
}

int main() {
    n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        E[u].emplace_back(v), E[v].emplace_back(u);
    }
    dfs(1, 0);
    int ans = 2ll * qpow(n, mod - 3) % mod * f[1][1][1] % mod;
    printf("%d\n", ans);
    return 0;
}