题面

题目描述

小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。

这个树的边是一条一条添加上去的。

在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了 $5$ 条边。其中， $(3,8)$ 这条边的负载是 $6$ ，因为有六条简单路径 $2-3-8$ , $2-3-8-7$ , $3-8,3-8-7$ , $4-3-8$ , $4-3-8-7$ 路过了 $(3,8)$ 。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

输入格式

第一行包含两个整数 $N, Q$ ,表示星球的数量和操作的数量。星球从 $1$ 开始编号。

接下来的 $Q$ 行，每行是如下两种格式之一：

A x y 表示在 $x$ 和 $y$ 之间连一条边。保证之前 $x$ 和 $y$ 是不联通的。
Q x y表示询问 $(x,y)$ 这条边上的负载。保证 $x$ 和 $y$ 之间有一条边。

输出格式

对每个查询操作，输出被查询的边的负载。

样例 #1

样例输入 #1

样例输出 #1

提示

对于所有数据， $1≤N,Q≤10^5$

思路

对于一条路径 $u \leftrightarrow u$ ，它的当前负载为 $u$ 所在连通块的大小 $siz_u$ 与 $v$ 所在连通块的大小 $siz_v$ 的乘积。

问题在于如何动态维护这样一个子树大小。

根据样例，我们发现最后建成的是一个森林，那么我们可以加一个虚拟源点，连接每个连通块把它变成一颗树。

这样我们可以在新树上做树剖，转化为区间操作问题。

然后我们重新看每次的操作，如果是加边 $x \leftrightarrow y$ ，先判断一下它们在新树上的关系，把儿子所在的连通块合并给父亲所在的连通块，这样可以保证它们树上的位置关系不变，可以用树剖出的区间做处理，并用并查集维护它们连通块的根，而当前状态连通块的大小需要把 $x$ 到 $root_x$ 的路径上所有的点的权值加上 $y$ 当前的子树大小，单点修改、区间查询，可以用差分维护树状数组，这里我写的是线段树。

易错点：

由于加了一个虚拟源点，所以树剖后的区间为 $[1,n+1]$ ，所以我们线段树的右界为 $n + 1$ （虽然用不上 $[1,1]$ ）。
开 LL。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
#define ls(x) tr[u << 1]
#define rs(x) tr[u << 1 | 1]
namespace SegmentTree
{
    struct Node
    {
        int l, r;
        LL sum, add;
    }tr[N << 2];
    void pushup(int u)
    {
        tr[u].sum = ls(u).sum + rs(u).sum;
    }
    void pushdown(int u)
    {
        Node &root = tr[u];
        if(root.add)
        {
            ls(u).add += root.add;
            rs(u).add += root.add;
            ls(u).sum += (LL)(ls(u).r - ls(u).l + 1) * root.add;
            rs(u).sum += (LL)(rs(u).r - rs(u).l + 1) * root.add;
            root.add = 0;
        }
    }
    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r;
        if(l == r)
        {
            tr[u].sum = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
    void update(int u, int l, int r, LL k)
    {
        if(l <= tr[u].l && tr[u].r <= r)
        {
            tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * k;
            tr[u].add += k;
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) update(u << 1, l, r, k);
        if(r > mid) update(u << 1 | 1, l, r, k);
        pushup(u);
    }
    LL query(int u, int x)
    {
        if(tr[u].l == tr[u].r) return tr[u].sum;
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) return query(u << 1, x);
        else return query(u << 1 | 1, x);
    }
}

int n, m, Root;
int cnt, idx, tot;
bool vis[N];
int fir[N], p[N], id[N], top[N], sz[N], fa[N], dep[N], son[N];
struct Edge
{
    int nxt, to;
}e[N << 2];
struct Request
{
    int x, y;
    bool bj; // 0 - 边 1 - 查
}q[N];

void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    fir[u] = cnt;
}
void dfs1(int u)
{
    sz[u] = 1;
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[u]) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}
void dfs2(int u, int t)
{
    if(vis[u]) return;
    vis[u] = true;
    top[u] = t;
    id[u] = ++idx;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
LL query_tree(int x)
{
    return SegmentTree::query(1, id[x]);
}
void update(int x, int y)
{
    int root = find(x);
    LL sum = query_tree(y);
    while(top[x] != top[root])
    {
        SegmentTree::update(1, id[top[x]], id[x], sum);
        x = fa[top[x]];
    }
    SegmentTree::update(1, id[root], id[x], sum);
    p[find(y)] = root;
}
LL query(int x, int y)
{
    LL qx = query_tree(find(x));
    LL qy = query_tree(y);
    return (qx - qy) * qy;
}

int main()
{
    scanf("%d%d", &n, &m);
    Root = n + 1;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        char op = '\0';
        while(op != 'A' && op != 'Q') op = getchar();
        int x, y;
        scanf("%d%d", &x, &y);
        if(op == 'A')
        {
            add(x, y);
            add(y, x);
            q[++tot] = {x, y, false};
            p[find(y)] = find(x);
        }
        else q[++tot] = {x, y, true};
    }
    for(int i = 1; i <= n; i++)
        if(find(i) == i)
            add(i, Root), add(Root, i);
    dep[Root] = 1;
    dfs1(Root);
    dfs2(Root, Root);
    for(int i = 1; i <= n; i++) p[i] = i;
    SegmentTree::build(1, 1, n + 1);
    for(int i = 1; i <= tot; i++)
    {
        if(fa[q[i].x] == q[i].y) swap(q[i].x, q[i].y);
        if(!q[i].bj) update(q[i].x, q[i].y);
        else printf("%lld\n", query(q[i].x, q[i].y));
    }
    return 0;
}

2023-10-12 11:59:37 # OI # Problem #树链剖分