Statement

给你一棵 nn 个点的森林，点有黑白两种颜色，初始时全为白色，边带权。初始时森林有 mm 条边。请你支持 qq 次操作：加边；删边；翻转 uu 的颜色；询问 uu 所在的树中所有黑点到它的距离之和。

数据范围：m<n≤105m<n\le10^5，k≤3×105k\le3\times10^5，∣w∣≤107|w|\le10^7。

Solution

边权肯定要拆成点权。难点主要是 LCT 的 MakeRoot 中，翻转根节点时不能维护好答案。所以对于每个 xx，要维护到所在 Splay 深度最浅的点的距离和，以及到所在 Splay 深度最深的点的距离和。

具体而言，对于每个 xx，都需要维护：

  • 颜色（11 为黑，虚拟节点全为白）：col\text{col}
  • 虚子树内黑点个数：vcnt\text{vcnt}
  • 虚子树和 Splay 子树内黑点个数：cnt\text{cnt}
  • 虚子树内黑点到 xx 的距离和：vans\text{vans}
  • 虚子树和 Splay 子树内黑点到 Splay 深度最浅的点的距离和：lans\text{lans}
  • 虚子树和 Splay 子树内黑点到 Splay 深度最深的点的距离和：rans\text{rans}
  • 边权（如果有的话）：val\text{val}
  • Splay 子树内边权和：sum\text{sum}

合并的时候，已知 col,vcnt,vans,val\text{col},\text{vcnt},\text{vans},\text{val}，需要计算 cnt,lans,rans,sum\text{cnt},\text{lans},\text{rans},\text{sum}。

cnt\text{cnt} 和 sum\text{sum} 的计算很简单：

cnt(x)=[col(x)=1]+vcnt(x)+cnt(lson(x))+cnt(rson(x))sum(x)=val(x)+sum(lson(x))+sum(rson(x))\begin{aligned} \text{cnt}(x)&=[\text{col}(x)=1]+\text{vcnt}(x)+\text{cnt}(\text{lson}(x))+\text{cnt}(\text{rson}(x))\\ \text{sum}(x)&=\text{val}(x)+\text{sum}(\text{lson}(x))+\text{sum}(\text{rson}(x)) \end{aligned}

需要理解的是 lans\text{lans} 和 rans\text{rans} 的计算：

lans(x)= vans(x)+lans(lson(x))+lans(rson(x))+([col(x)=1]+vcnt(x)+cnt(lson(x)))⋅(val(x)+sum(rson(x)))rans(x)= vans(x)+rans(lson(x))+rans(rson(x))+([col(x)=1]+vcnt(x)+cnt(rson(x)))⋅(val(x)+sum(lson(x)))\begin{aligned} \text{lans}(x)=&~\text{vans}(x)+\text{lans}(\text{lson}(x))+\text{lans}(\text{rson}(x))\\ &+([\text{col}(x)=1]+\text{vcnt}(x)+\text{cnt}(\text{lson}(x)))\cdot(\text{val}(x)+\text{sum}(\text{rson}(x)))\\ \text{rans}(x)=&~\text{vans}(x)+\text{rans}(\text{lson}(x))+\text{rans}(\text{rson}(x))\\ &+([\text{col}(x)=1]+\text{vcnt}(x)+\text{cnt}(\text{rson}(x)))\cdot(\text{val}(x)+\text{sum}(\text{lson}(x))) \end{aligned}

时间复杂度 O(nlog⁡n)O(n\log n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
namespace IO {
template <class T>
void input(T& x) {
    bool f;
    char c;
    for (f = 0; !isdigit(c = getchar());)
        if (c == '-') f = 1;
    for (x = 0; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
    if (f) x = -x;
}
template <class T>
void output(T x, char c = '\n') {
    static char f[97];
    int pf = 0;
    if (!x) return putchar('0'), putchar(c), void();
    if (x < 0) x = -x, putchar('-');
    while (x) f[pf++] = x % 10 + '0', x /= 10;
    while (pf) putchar(f[--pf]);
    putchar(c);
}
}  // namespace IO
using namespace IO;
typedef long long LL;
const int N = 1e6 + 7;
int n, m, q;
namespace LCT {
struct Node* null;
struct Node {
    Node *pre, *son[2];
    bool rev, col;
    int vcnt, cnt;
    LL vans, lans, rans, val, sum;
    bool get() const { return pre->son[1] == this; }
    bool isRoot() const { return pre->son[0] != this && pre->son[1] != this; }
    void connect(Node* x, bool id) {
        if (this != null) son[id] = x;
        if (x != null) x->pre = this;
    }
    void reverse() { rev ^= 1, std::swap(son[0], son[1]), std::swap(lans, rans); }
    void pushup() {
        cnt = col + vcnt + son[0]->cnt + son[1]->cnt;
        lans = vans + son[0]->lans + son[1]->lans + (col + vcnt + son[1]->cnt) * (val + son[0]->sum);
        rans = vans + son[0]->rans + son[1]->rans + (col + vcnt + son[0]->cnt) * (val + son[1]->sum);
        sum = val + son[0]->sum + son[1]->sum;
    }
    void pushdown() {
        if (rev) {
            if (son[0] != null) son[0]->reverse();
            if (son[1] != null) son[1]->reverse();
            rev = 0;
        }
    }
    void rotate() {
        Node *y = pre, *z = y->pre;
        bool k = get(), kk = y->get(), t = y->isRoot();
        y->connect(son[k ^ 1], k), connect(y, k ^ 1);
        if (t)
            pre = z;
        else
            z->connect(this, kk);
        y->pushup(), pushup();
    }
} pool[N], *tail;
void splay(Node* x) {
    static Node* stk[N];
    int pstk = 0;
    Node* y = stk[++pstk] = x;
    while (!x->isRoot()) stk[++pstk] = x = x->pre;
    while (pstk) stk[pstk--]->pushdown();
    for (x = y; !x->isRoot(); x->rotate())
        if (!(y = x->pre)->isRoot()) (x->get() == y->get() ? y : x)->rotate();
}
void access(Node* x) {
    for (Node* y = null; x != null; x = (y = x)->pre)
        splay(x), x->vcnt += x->son[1]->cnt - y->cnt,
            x->vans += x->son[1]->lans - y->lans,
            x->connect(y, 1), x->pushup();
}
void makeRoot(Node* x) { access(x), splay(x), x->reverse(); }
void init(int n) {
    *(null = pool) = {null, {null, null}, 0, 0, 0, 0, 0, 0, 0, 0, 0}, tail = pool + n;
    for (int i = 1; i <= n; i++) *(pool + i) = *null, (pool + i)->sum = 1;
}
Node* newNode(int w) { return *++tail = *null, tail->val = tail->sum = w, tail; }
void link(int u, int v, int w) {
    Node *x = pool + u, *y = pool + v, *z = newNode(w);
    makeRoot(x), makeRoot(y);
    y->pre = z, z->vcnt += y->cnt, z->vans += y->lans, z->pushup();
    z->pre = x, x->vcnt += z->cnt, x->vans += z->lans, x->pushup();
}
void split(Node* x, Node* y) { makeRoot(y), access(x), splay(x); }
void cut(int u, int v) {
    Node *x = pool + u, *y = pool + v;
    split(x, y);
    Node* z = x->son[0];
    split(y, z), y->son[0] = z->pre = null, y->pushup();
    split(x, z), x->son[0] = z->pre = null, x->pushup();
}
void flip(int u) {
    Node* x = pool + u;
    makeRoot(x), x->col ^= 1, x->pushup();
}
LL query(int u) {
    Node* x = pool + u;
    return makeRoot(x), x->lans;
}
}  // namespace LCT
int main() {
    input(n), input(m), input(q), LCT::init(n);
    for (int i = 1, u, v, w; i <= m; i++) input(u), input(v), input(w), LCT::link(u, v, w);
    while (q--) {
        static char opt[5];
        int u, v, w;
        scanf("%s", opt), input(u);
        if (*opt == 'L')
            input(v), input(w), LCT::link(u, v, w);
        else if (*opt == 'C')
            input(v), LCT::cut(u, v);
        else if (*opt == 'F')
            LCT::flip(u);
        else
            output(LCT::query(u));
    }
    return 0;
}