BZOJ 1180 [CROATIAN2009]OTOCI Link Cut Trees

Description

給出n個結點以及每個點初始時對應的權值wi。起始時點與點之間沒有連邊。有3類操作： 1、bridge A B：詢問結點A與結點B是否連通。如果是則輸出“no”。否則輸出“yes”，并且在結點A和結點B之間連一條無向邊。 2、penguins A X：将結點A對應的權值wA修改為X。 3、excursion A B：如果結點A和結點B不連通，則輸出“impossible”。否則輸出結點A到結點B的路徑上的點對應的權值的和。給出q個操作，要求線上處理所有操作。資料範圍：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

Input

第一行包含一個整數n(1<=n<=30000)，表示節點的數目。第二行包含n個整數，第i個整數表示第i個節點初始時對應的權值。第三行包含一個整數q(1<=n<=300000)，表示操作的數目。以下q行，每行包含一個操作，操作的類别見題目描述。任意時刻每個節點對應的權值都是1到1000的整數。

Output

輸出所有bridge操作和excursion操作對應的輸出，每個一行。

Sample Input

5

4 2 4 5 6

10

excursion 1 1

excursion 1 2

bridge 1 2

excursion 1 2

bridge 3 4

bridge 3 5

excursion 4 5

bridge 1 3

excursion 2 4

excursion 2 5

Sample Output

4

impossible

yes

6

yes

yes

15

yes

15

16

HINT

​​傳送門​​

LCT的模闆題目……

之前怎麼就沒發現沒有這道基礎題呢？？？

最坑的是時限50s……

然後我第一發樣例過了很開心就送出……然後發現……

我Rotate裡面有個判斷打錯了！

最好WA吧……

結果就TLE了  = =  汗。。。。

改好之後就A了……跑了5000ms+

感覺跑的時間主要花在我建立這麼多子程式= =

有些隻用了1遍這樣= =

不過更加清晰嘛。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    N=30005;
int n;
struct LCT{
    int pre,son[2],sum,num;
    bool rev;
}tree[N];
bool isroot(int x){
    return tree[tree[x].pre].son[0]!=x &&
        tree[tree[x].pre].son[1]!=x;
}
void up(int x){
    if (x){
        int l=tree[x].son[0],r=tree[x].son[1];
        tree[x].sum=tree[x].num;
        if (l) tree[x].sum+=tree[l].sum;
        if (r) tree[x].sum+=tree[r].sum;
    }
}
void down(int x){
    if (x && tree[x].rev){
        int l=tree[x].son[0],r=tree[x].son[1];
        swap(tree[x].son[0],tree[x].son[1]);
        tree[l].rev^=1,tree[r].rev^=1,
        tree[x].rev^=1;
    }
}
void Rotate(int x){
    int y=tree[x].pre,z=tree[y].pre,l,r;
    if (tree[y].son[0]==x) l=0; else l=1;
    r=l^1;
    if (!isroot(y))
        if (tree[z].son[0]==y) tree[z].son[0]=x;
            else tree[z].son[1]=x;
    tree[x].pre=z,tree[y].pre=x;
    tree[y].son[l]=tree[x].son[r];
    tree[tree[x].son[r]].pre=y;
    tree[x].son[r]=y;
    up(y);
}
int stk[N];
void splay(int x){
    int top=1;stk[1]=x;
    for (int i=x;!isroot(i);i=tree[i].pre)
        stk[++top]=tree[i].pre;
    while (top) down(stk[top--]);
    while (!isroot(x)){
        int y=tree[x].pre,z=tree[y].pre;
        if (!isroot(y))
            if (tree[y].son[0]==x^tree[z].son[0]==y) Rotate(x);
                else Rotate(y);
        Rotate(x);
    }
    up(x);
}
void access(int x){
    for (int t=0;x;t=x,x=tree[x].pre)
        splay(x),tree[x].son[1]=t,up(x);
}
void makeroot(int x){
    access(x),splay(x);
    tree[x].rev^=1;
}
void split(int x,int y){
    makeroot(x);
    access(y),splay(y);
}
void link(int x,int y){
    makeroot(x);
    tree[x].pre=y;
    up(y);
}
int findroot(int x){
    access(x),splay(x);
    while (tree[x].son[0]) x=tree[x].son[0];
    return x;
}
bool sameset(int x,int y){
    return findroot(x)==findroot(y);
}
int querysum(int x,int y){
    split(x,y);
    return tree[y].sum;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++)
        tree[i].num=read();
    int q=read(),x,y;
    char opt[15];
    while (q--){
        scanf("%s",opt);
        x=read(),y=read();
        if (opt[0]=='b')
            if (sameset(x,y)) puts("no");
                else puts("yes"),link(x,y);
        if (opt[0]=='p')
            tree[x].num=y,splay(x);
        if (opt[0]=='e')
            if (!sameset(x,y)) puts("impossible");
                else printf("%d\n",querysum(x,y));
    }
    return 0;
}