题解 | #Flower_Rainbow_and_Game#

树形dp

考虑以 $u$ 为根的子树

先考虑 $u$ 的每个儿子对于答案的贡献，明显是各个子树大小之和。
再考虑跨越根节点 $u$ 的各个子树之间的答案，先任意找两棵子树 $S_{1}$ 和 $S_{2}$ ，假设他们的根节点为 $v_{1}$ 与 $v_{2}$ 他们之间产生的答案是

\begin{aligned} \sum_{i\in{S_{1}}}\sum_{j\in{S_{2}}}deepth(i) + deepth(j) = size(v2)alldeepth(v1) + size(v1)alldeepth(v2) \end{aligned}

这里的 $alldeepth$ 是子树上各个节点深度之和，这样单独一棵子树 $S_{k}$ 对答案的贡献就可以很好的算出来了，这里用 $S$ 代表子树的集合

\begin{aligned} \sum_{i\in{S},i\neq{k}}size(i)*alldeepth(k) \end{aligned}

下面贴代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i = a ; i <= b ; i++)
#define per(i,a,b) for(int i = a ; i >= b ; i--)
using namespace std;
const int MOD = 998244353;
const int MAXN = 2e5 + 10;
int alldeepth[MAXN],si[MAXN];
vector<int> graph[MAXN];
int ans = 0;
void dfs(int u,int fa) {
    si[u] = 1;
    int sum = 0;
    int num = 0;
    for (auto& v : graph[u]) {
        if (v == fa)continue;
        dfs(v,u);
        alldeepth[u] += alldeepth[v];
        si[u] += si[v];
        sum = (sum + si[v])%MOD;
        ans = (ans + si[v]) % MOD;
        num++;
    }
    alldeepth[u] += si[u];
    if (num <= 1)return;
    for (auto& v : graph[u]) {
        if (v == fa)continue;
        ans = (ans + ((sum - si[v])%MOD + MOD) % MOD * alldeepth[v] % MOD) % MOD;
    }
}
void solve() {
    int n;
    cin >> n;
    ans = 0;
    rep(i,0,n) {
        graph[i].clear();
        alldeepth[i] = 0;
        si[i] = 0;
    }
    rep(i,1,n-1) {
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1,0);
    cout << ans << endl;
}
signed main() {
    IOS;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}