P9584 城市 题解。

1. 题意

给出一棵 $n$ 个点的树，边有边权，每次询问添加一个点 $n + 1$ 和一条边 $(u, n + 1)$ 后任意两点之间的距离和。

2. 题解

考虑一条边对答案的贡献，即为通过这条边的路径数 $\times$ 边权。

为了方便计算，我们将边的贡献转为点的贡献：设 $a_u$ 表示 $u$ 到父亲的边权，$f_u$ 表示子树大小，$g_u = n - f_u$ 表示子树外大小，则点 $u$ 的贡献为 $a_u \cdot f_u \cdot g_u$。

然后考虑加了一条边 $(u, n + 1)$ 之后怎么算，不妨设 $u$ 是 $n + 1$ 的父亲。于是 $u$ 到根路径上每个点的子树大小都要 $+1$，其余点的子树外大小都要 $+1$，另外答案还要加上新边的贡献。

这样对于每个询问暴力加边计算是 $O(nm)$ 的，但其实可以直接预处理。发现新边的贡献比较好算，即 $n \cdot w$，于是考虑预处理每个点除去新边的贡献的答案。

我们先 DFS 预处理出每个点的 $a_u$、$f_u$、$g_u$，另外因为加了一个点所以预处理子树外大小时 $g_u = n + 1 - f_u$。

然后我们再 DFS 一遍求出每个点的答案，当遍历到一个点 $u$ 时 $f_u \gets f_u + 1$，$g_u \gets g_u - 1$，同时更新当前答案，回溯时再改回来即可。

最后处理询问的时候，将预处理的答案加上新边贡献即可，然后还要 $\times 2$ 因为每条路径要算两次。

时间复杂度 $O(n + m)$。

3. Code

                
#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;
const int N = 2e5 + 5, P = 998244353;
int n, m, a[N], f[N], g[N], ans[N], cur;
vector<pair<int, int>> G[N];
void dfs1(int u, int fa) {
    f[u] = 1;
    for (auto [v, w] : G[u])
        if (v != fa) a[v] = w, dfs1(v, u), f[u] += f[v];
    g[u] = n + 1 - f[u];
    cur = (cur + (i64)a[u] * f[u] * g[u]) % P;
}
void dfs2(int u, int fa) {
    cur = (cur - (i64)a[u] * f[u] * g[u] + P) % P;
    ++f[u], --g[u];
    cur = (cur + (i64)a[u] * f[u] * g[u]) % P;
    ans[u] = cur;
    for (auto [v, w] : G[u])
        if (v != fa) dfs2(v, u);
    cur = (cur - (i64)a[u] * f[u] * g[u] + P) % P;
    --f[u], ++g[u];
    cur = (cur + (i64)a[u] * f[u] * g[u]) % P;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= n - 1; i++) {
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1, u, w; i <= m; i++) {
        cin >> u >> w;
        cout << (ans[u] + (i64)n * w) * 2 % P << '\n';
    }
    return 0;
}
                
cpp