P10658 BZOJ2959 长跑
大意
题目要求我们在设定边方向后，使 \(A\) 到 \(B\) 路径上的刷卡次数最多。
思路
此题的关键在于，我们道路的方向是可以自己确定的，可这有什么用呢？
如果我们碰到了一个环，那么我们直接把环上的所有道路沿着一个方向，由于我们是可以重复走的，所以我们一定可以把一个环走完。
那知道了这个之后呢？我们先把这些边双连通缩成点，由于某些点的权值是会变换，边也会变化，也就是说，我们需要维护的是一个动态的树，或者说是一个森林。
但是我们的 LCT 无法处理与环有关的问题，我们采用并查集协助维护。具体来说，我们用数组 \(f\) 来维护缩点，\(f[i]\) 就代表点 \(i\) 所属的边双连通的代表元。所有在涉及有关 LCT 操作的时候，我们的 \(fa(x)\) 都要写成 \(find(fa(x))\)，这是一个易错点。
特别的，我们的连边函数发生了变化，如果不成环，那就无所谓，还是按照原来的方式，如果是成环了，那就直接提取 \(x \to y\) 的路径，通过递归暴力缩点，由于每个点只会被缩一次，所以均摊复杂度很低。
询问答案的时候，要注意连通性，如果连通就直接提取路径，查询答案即可。
代码
#include<iostream>
#include<cstdio>
using namespace std;#define uint unsigned int
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 150005;struct node{int ch[2], fa;uint val, sum;bool tag;node(){ch[1] = ch[0] = fa = 0;val = sum = 0;tag = false;}
}t[MAXN];int f[MAXN];
uint real[MAXN];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }bool isroot(int x){int faf = find(fa(x));return (lc(faf) != x) && (rc(faf) != x);
}void pushup(int x){t[x].sum = t[lc(x)].sum + t[rc(x)].sum + t[x].val;
}void update_rev(int x){if(!x) return;int tmp = lc(x); lc(x) = rc(x); rc(x) = tmp;t[x].tag ^= 1;
}void pushdown(int x){if(t[x].tag){update_rev(lc(x));update_rev(rc(x));t[x].tag = 0;}
}void rotate(int x){int y = find(fa(x)), z = find(fa(y));int k = (rc(y) == x);if(!isroot(y)){t[z].ch[rc(z) == y] = x;}fa(x) = z;t[y].ch[k] = t[x].ch[k ^ 1];if(t[x].ch[k ^ 1]){fa(t[x].ch[k ^ 1]) = y;}t[x].ch[k ^ 1] = y;fa(y) = x;pushup(y);pushup(x);
}void pushshell(int x){if(!isroot(x)){pushshell(find(fa(x)));}pushdown(x);
}void splay(int x){x = find(x);pushshell(x);while(!isroot(x)){int y = find(fa(x)), z = find(fa(y));if(!isroot(y)){(rc(z) == y) == (rc(y) == x) ? rotate(y) : rotate(x);}rotate(x);}
}void access(int x){for(int y = 0;x;y = x, x = find(fa(x))){splay(x);rc(x) = y;pushup(x);}
}void makeroot(int x){x = find(x);access(x);splay(x);update_rev(x);
}void split(int x, int y){makeroot(x);access(y);splay(y);
}int findrt(int x){access(x);splay(x);while(lc(x)){pushdown(x);x = lc(x);}splay(x);return x;
}void merge(int x, int rt){if(!x) return;f[find(x)] = find(rt);if(x != rt) t[rt].val += t[x].val;merge(lc(x), rt);merge(rc(x), rt);lc(x) = rc(x) = 0;
}void link(int x, int y){x = find(x); y = find(y);if(x == y) return;if(findrt(x) != findrt(y)){makeroot(x);fa(x) = y;}else{split(x, y);merge(lc(y), y);pushup(y);}
}int main(){int n, m;scanf("%d %d", &n, &m);for(int i = 1;i <= n;i ++){f[i] = i;scanf("%u", &real[i]);t[i].val = t[i].sum = real[i];}while(m --){int op, u, v;scanf("%d %d %d", &op, &u, &v);if(op == 1){link(u, v);}else if(op == 2){int ru = find(u);splay(ru);t[ru].val += (uint)v - real[u];real[u] = v;pushup(ru);}else if(op == 3){int ru = find(u), rv = find(v);if(findrt(ru) != findrt(rv)) printf("-1\n");else{split(ru, rv);printf("%u\n", t[rv].sum);}}}return 0;
}