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 双连通分量 并查集]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。