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;
}