2959: 长跑

题意：字词加入边，修改点权，询问两点间走一条路径的最大点权和。不一定是树

---

不是树?

把边双连通分量缩为一点！

怎么缩？

用一个并查集维护连通性，另一个并查集维护每个点所在边双的编号，初始化就是自己。

加边(x,y)的时候，如果形成环，那么把x到y的路径提取出来，把这个splay变成一个点就行了

注意：其他的点会有父亲连向缩点的bcc中的其他点，access的时候会用到轻边连向的父亲，需要使用并查集来找fa，并且要重设父亲，一开始没处理这里

清橙上T了4个点

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define lc t[x].ch[0] #define rc t[x].ch[1] #define pa t[x].fa typedef long long ll; const int N=3e5+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int n, Q, op, x, y, val[N]; struct ufs {int fa[N];int find(int x) {return x==fa[x] ? x : fa[x]=find(fa[x]);}inline void unn(int x, int y) {fa[find(x)]=find(y);}inline void ini(int n) {for(int i=1; i<=n; i++) fa[i]=i;} }a, b;namespace lct {struct meow {int ch[2], fa, rev, sum, w;} t[N];inline int wh(int x) {return t[pa].ch[1] == x;}inline int isr(int x) {return t[pa].ch[0] != x && t[pa].ch[1] != x;}inline void update(int x) {t[x].sum = t[lc].sum + t[rc].sum + t[x].w;}inline void rever(int x) {t[x].rev ^= 1; swap(lc, rc);}inline void pushdn(int x) {if(t[x].rev) {if(lc) rever(lc);if(rc) rever(rc);t[x].rev = 0;}}void pd(int x) {if(!isr(x)) pd(pa); pushdn(x);}inline void rotate(int x) {int f=t[x].fa, g=t[f].fa, c=wh(x);if(!isr(f)) t[g].ch[wh(f)]=x; t[x].fa=g;t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa=f;t[x].ch[c^1]=f; t[f].fa=x;update(f); update(x);}inline void splay(int x) {pd(x);for(; !isr(x); rotate(x))if(!isr(pa)) rotate(wh(x)==wh(pa) ? pa : x);}void see(int x) {if(lc) see(lc); printf("%d ",x); if(rc) see(rc);}inline void access(int x) {for(int y=0; x; y=x, x = b.find(pa)) // light_fasplay(x), rc=y, t[y].fa=x, update(x);}inline void maker(int x) {access(x); splay(x); rever(x);}inline void link(int x, int y) { //printf("lct::link %d %d\n",x,y);maker(x); t[x].fa=y;}inline void split(int x, int y) { //printf("split %d %d\n",x,y);maker(x); access(y); splay(y); //printf("yyy %d %d %d\n",y,t[y].ch[0],t[y].sum);}int q[N], head, tail;inline void rebuild(int x, int y) { //all(x, y) --> ysplit(x, y);//see(y); puts(" see");head=tail=1; q[tail++]=y;while(head != tail) {int x = q[head++]; b.fa[x] = y; //printf("x %d\n",x);if(lc) q[tail++]=lc;if(rc) q[tail++]=rc;lc = rc = 0;}t[y].w = t[y].sum;}}void Link(int x, int y) {x = b.find(x); y = b.find(y);if(x == y) return;int f1=a.find(x), f2=a.find(y); //printf("\nLink %d %d %d %d\n",x,y,f1,f2);if(f1 != f2) lct::link(x, y), a.unn(x, y);else lct::rebuild(x, y); } void Add(int x, int y) {x = b.find(x);lct::t[x].w += y; lct::splay(x); } int Que(int x, int y) { //printf("\nQue %d %d\n",x,y);if(a.find(x) != a.find(y)) return -1;x = b.find(x); y = b.find(y); //printf("x y %d %d\n",x,y);if(x == y) return lct::t[x].w;lct::split(x, y);return lct::t[y].sum; }int main() {freopen("in","r",stdin);n=read(); Q=read();a.ini(n); b.ini(n);for(int i=1; i<=n; i++) val[i] = lct::t[i].w = read();for(int i=1; i<=Q; i++) { //puts("");op=read(); x=read(); y=read();if(op==1) Link(x, y);if(op==2) Add(x, y-val[x]), val[x]=y;if(op==3) printf("%d\n", Que(x, y));} }

总结

以上是生活随笔为你收集整理的BZOJ 2959: 长跑 [lct 双连通分量 并查集]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。