LCT新姿势：维护边双连通分量。
题意：给你一张无向图，有加边，改点权操作。
你需要回答的是：从a到b，给每条边任意定向后，能经过的点权之和最大是多少。(每个点只算一次，点权非负)。
可以发现，一个边双连通分量之内的都可以到达。就相当于在缩点后的树上求路径权值和。
使用LCT动态维护：开两个并查集。
一个维护连通性，一个维护缩点后的代表点。
当我们连接两个已经联通的点的时候，把他们之间的那一条路径上的点所在的边双全部缩到某个代表点上，该点的权值也要相应的变化，然后删掉这一条路径上的其他点。查询和修改就是正常姿势。
具体实现如何缩点：
首先提取这一条链成为一颗splay，然后遍历这个splay并全部把代表点设为某个点(splay的根)。最后把这个树删的只剩根。
那么有些虚边如何处理？要用fa[x]的时候用belong.find(fa[x])即可。权值在并查集里面记录。
你相当于在lct上把这些点删了，所有指向这些点的边都指向了代表点。所以当你重新提取一条链的时候，每个点都是一个代表点，不会有之前被删的点存在。
1 #include2 #include 3 4 const int N = 150010; 5 6 int fa[N], s[N][2], val[N], sum[N], S[N], Sp; 7 bool rev[N]; 8 9 inline void read(int &x) { 10 x = 0; 11 char c = getchar(); 12 while(c < '0' || c > '9') { 13 c = getchar(); 14 } 15 while(c >= '0' && c <= '9') { 16 x = (x << 3) + (x << 1) + c - 48; 17 c = getchar(); 18 } 19 return; 20 } 21 22 struct UFS { 23 int fa[N], Val[N]; 24 inline void init(int n) { 25 for(int i = 1; i <= n; i++) { 26 fa[i] = i; 27 Val[i] = val[i]; 28 } 29 return; 30 } 31 int find(int x) { 32 if(fa[x] == x) { 33 return x; 34 } 35 return fa[x] = find(fa[x]); 36 } 37 inline void merge(int x, int y) { 38 x = find(x); 39 y = find(y); 40 if(x != y) { 41 fa[y] = x; 42 Val[x] += Val[y]; 43 } 44 return; 45 } 46 inline bool check(int x, int y) { 47 return find(x) == find(y); 48 } 49 }ufs, belong; 50 51 inline bool no_root(int x) { 52 int f = belong.find(fa[x]); 53 return (s[f][0] == x) || (s[f][1] == x); 54 } 55 56 inline void pushup(int x) { 57 sum[x] = sum[s[x][0]] + sum[s[x][1]] + belong.Val[x]; 58 return; 59 } 60 61 inline void pushdown(int x) { 62 if(rev[x]) { 63 if(s[x][0]) { 64 rev[s[x][0]] ^= 1; 65 } 66 if(s[x][1]) { 67 rev[s[x][1]] ^= 1; 68 } 69 std::swap(s[x][0], s[x][1]); 70 rev[x] = 0; 71 } 72 return; 73 } 74 75 inline void rotate(int x) { 76 int y = belong.find(fa[x]); 77 int z = belong.find(fa[y]); 78 bool f = (s[y][1] == x); 79 80 fa[x] = z; 81 if(no_root(y)) { 82 s[z][s[z][1] == y] = x; 83 } 84 s[y][f] = s[x][!f]; 85 if(s[x][!f]) { 86 fa[s[x][!f]] = y; 87 } 88 s[x][!f] = y; 89 fa[y] = x; 90 91 pushup(y); 92 pushup(x); 93 return; 94 } 95 96 inline void splay(int x) { 97 int y = x; 98 S[++Sp] = y; 99 while(no_root(y)) {100 y = belong.find(fa[y]);101 S[++Sp] = y;102 }103 while(Sp) {104 pushdown(S[Sp]);105 Sp--;106 }107 108 y = belong.find(fa[x]);109 int z = belong.find(fa[y]);110 while(no_root(x)) {111 if(no_root(y)) {112 (s[z][1] == y) ^ (s[y][1] == x) ?113 rotate(x) : rotate(y);114 }115 rotate(x);116 y = belong.find(fa[x]);117 z = belong.find(fa[y]);118 }119 return;120 }121 122 inline void access(int x) {123 int y = 0;124 while(x) {125 splay(x);126 s[x][1] = y;127 pushup(x);128 y = x;129 x = belong.find(fa[x]);130 }131 return;132 }133 134 inline void make_root(int x) {135 access(x);136 splay(x);137 rev[x] = 1;138 return;139 }140 141 inline void link(int x, int y) {142 make_root(x);143 fa[x] = y;144 return;145 }146 147 void del(int x, int r) {148 belong.merge(r, x);149 if(s[x][0]) {150 del(s[x][0], r);151 }152 if(s[x][1]) {153 del(s[x][1], r);154 }155 s[x][0] = s[x][1] = 0;156 pushup(x);157 return;158 }159 160 int main() {161 int n, m;162 read(n);163 read(m);164 for(int i = 1; i <= n; i++) {165 read(val[i]);166 }167 ufs.init(n);168 belong.init(n);169 for(int i = 1, x, y, f; i <= m; i++) {170 read(f);171 read(x);172 read(y);173 if(f == 1) { // link174 x = belong.find(x);175 y = belong.find(y);176 if(!ufs.check(x, y)) {177 ufs.merge(x, y);178 link(x, y);179 }180 else if(!belong.check(x, y)){181 make_root(x);182 access(y);183 splay(y);184 del(y, y);185 }186 }187 else if(f == 2) { // val a -> b188 int tx = belong.find(x);189 make_root(tx);190 belong.Val[tx] += y - val[x];191 val[x] = y;192 pushup(tx);193 }194 else { //ask195 x = belong.find(x);196 y = belong.find(y);197 if(!ufs.check(x, y)) {198 puts("-1");199 }200 else {201 make_root(x);202 access(y);203 splay(y);204 printf("%d\n", sum[y]);205 }206 }207 }208 209 return 0;210 }
类似的题还有bzoj4998 星球联盟。