题解：CF855G Harry Vs Voldemort

· · 题解

本题需要动态维护边双连通分量并统计符合条件的三元组数量。

先考虑一开始的树的答案怎么统计，可以发现从 w 的角度去统计答案较为方便，设与 x 相连的点的集合为 S_x，若整棵树以 x 为根 y 的子树的大小为 sz_{x,y}，那么答案即为：

\sum_{x=1}^n\sum_{u\in S_x}\sum_{v\in S_x,u\neq v}sz_{x,u} \cdot sz_{x,v} =\sum_{x=1}^n((\sum_{u\in S_x}sz_{x,u})^2-\sum_{u\in S_x}sz_{x,u}^2)

如果要动态加边，我们可以在加边时将树上对应的一段路径上的所有点合并，并使用并查集维护已合并的节点，将已经合并的节点用最顶端的节点代替，就得到了边双连通分量缩点后的树。我们设原树为以 1 为根的有根树，设 son_x 表示 x 的儿子节点集合，s1_x 表示 x 的所有儿子子树大小和，s2_x 表示 x 的所有儿子子树大小平方和，cnt_x 表示 x 代表的边双连通分量中的节点数，cur_x 表示以 x 中某个点为中间节点的合法三元组数量，我们需要动态维护这四个值，即：

s1_x=\sum_{u\in son_x}sz_x \\ s2_x=\sum_{u\in son_x}sz_x^2 \\ cur_x=cnt_x(cnt_x-1)(cnt_x-2)+2cnt_x(cnt_x-1)(n-cnt_x)+(s1+n-sz_x)^2-s2_x-(n-sz_x)^2

同时我们动态维护答案就行了。

代码示例：

#include <iostream>

using namespace std;

using ll = long long;
constexpr int maxn = 100000, maxk = 16;
int head[maxn + 5], vert[2 * maxn + 5], nxt[2 * maxn + 5], tot;
int fa[maxn + 5][maxk + 5], top[maxn + 5], sz[maxn + 5], cnt[maxn + 5], dep[maxn + 5];
ll s1[maxn + 5], s2[maxn + 5], cur[maxn + 5];

inline void add(int x, int y)
{
    vert[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

int get(int x)                      //  并查集
{
    if (x == top[x]) return x;
    return top[x] = get(top[x]);
}

void dfs(int x, int f)             //  预处理
{
    dep[x] = dep[f] + 1; fa[x][0] = f;
    sz[x] = cnt[x] = 1;
    for (int i = 1; i <= maxk; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];

    for (int i = head[x]; i; i = nxt[i])
    {
        int y = vert[i];
        if (y == f) continue;
        dfs(y, x); sz[x] += sz[y];
        s1[x] += sz[y]; s2[x] += 1ll * sz[y] * sz[y];
    }
}

int lca(int x, int y)           // 求 LCA
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = maxk; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = maxk; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
        { x = fa[x][i]; y = fa[y][i]; }
    return fa[x][0];
}

inline ll calc2(int n)
{ return 1ll * n * (n - 1); }

inline ll calc3(int n)
{ return 1ll * n * (n - 1) * (n - 2); }

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        add(u, v); add(v, u);
    }
    dfs(1, 0);

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        top[i] = i;
        if (1 == i)
            cur[i] = s1[i] * s1[i] - s2[i];
        else
            cur[i] = (s1[i] + n - sz[i]) * (s1[i] + n - sz[i]) - s2[i] - 1ll * (n - sz[i]) * (n - sz[i]);
        ans += cur[i];
    }
    cout << ans << endl;           //   预处理最初的答案

    int q; cin >> q;
    while (q--)
    {
        int x, y; cin >> x >> y;
        int f = get(lca(x, y));
        x = get(x); y = get(y);

        ll cs1 = 0, cs2 = 0; int c = 0;
        while (x != f)           //   cs1,cs2,c 分别为新计算的 s1,s2,cnt
        {
            cs1 += s1[x] - sz[x];
            cs2 += s2[x] - 1ll * sz[x] * sz[x];
            c += cnt[x]; ans -= cur[x];
            int cf = get(fa[x][0]);
            top[x] = cf; x = cf;
        }
        while (y != f)
        {
            cs1 += s1[y] - sz[y];
            cs2 += s2[y] - 1ll * sz[y] * sz[y];
            c += cnt[y]; ans -= cur[y];
            int cf = get(fa[y][0]);
            top[y] = cf; y = cf;
        }
        cs1 += s1[f]; cs2 += s2[f];
        c += cnt[f]; ans -= cur[f];
        s1[f] = cs1; s2[f] = cs2; cnt[f] = c;     //  更新答案
        cur[f] = calc3(c) + 2 * calc2(c) * (n - c) + ((cs1 + n - sz[f]) * (cs1 + n - sz[f]) - cs2 - 1ll * (n - sz[f]) * (n - sz[f])) * c;
        cout << (ans += cur[f]) << endl;
    }

    return 0;
}