bzoj2843極地旅行社

bzoj2843極地旅行社

題意：

一些點，每個點有一個權值。有三種操作：點與點連邊，單點修改權值，求兩點之間路徑上點的權值和（需要判輸入是否合法）

題解：

以前一直想不通為什麼神犇們的模闆中LCT在link和cut後都要在根節點打翻轉标記。現在明白了，因為隻有這樣才能保持深度的正确性，以前沒有是以炸過是因為我以前都是把LCT拿來當鍊剖用的，根本不用link和cut~~這道題是LCT模闆題也沒什麼好說的。不過CCZ大爺有更快的做法，就是離線讀入所有連邊操作，然後建一棵樹用鍊剖，判斷輸入是否合法就線上用并查集查詢與維護。orzCCZ！

代碼：

1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 50000
 6 using namespace std;
 7 
 8 int fa[maxn],ch[maxn][2],sm[maxn],v[maxn];bool rev[maxn];
 9 inline void update(int x){
10     if(x==0)return; sm[x]=v[x];
11     if(ch[x][0])sm[x]+=sm[ch[x][0]]; if(ch[x][1])sm[x]+=sm[ch[x][1]];
12 }
13 inline bool is_root(int x){
14     if(x==0||fa[x]==0)return 1;
15     return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
16 }
17 inline void pushdown(int x){
18     if(rev[x]){
19         swap(ch[x][0],ch[x][1]); if(ch[x][0])rev[ch[x][0]]^=1; if(ch[x][1])rev[ch[x][1]]^=1; rev[x]^=1;
20     }
21 }
22 void rotate(int x){
23     if(x==0||is_root(x))return;
24     int a1=fa[x],a2=fa[fa[x]],a3; bool b1=(x==ch[a1][1]),b2=(a1==ch[a2][1]),b3=is_root(a1); a3=ch[x][!b1];
25     if(!b3)ch[a2][b2]=x; fa[x]=a2; ch[a1][b1]=a3; if(a3)fa[a3]=a1; ch[x][!b1]=a1; fa[a1]=x;
26     update(a1); update(x); if(!b3)update(a2);
27 }
28 int dt[maxn],dts,y;
29 void splay(int x){
30     if(x==0)return; dts=0; y=x; while(! is_root(y))dt[++dts]=y,y=fa[y];
31     dt[++dts]=y; while(dts)pushdown(dt[dts]),dts--;
32     while(!is_root(x)){
33         if(!is_root(fa[x]))((x==ch[fa[x]][1])^(fa[x]==ch[fa[fa[x]]][1]))?rotate(x):rotate(fa[x]);
34         rotate(x);
35     }
36 }
37 int access(int x){
38     if(x==0)return 0; int t=0;
39     while(x){splay(x); ch[x][1]=t; update(x); if(t)fa[t]=x; t=x; x=fa[x];}
40     return t;
41 }
42 bool link(int x,int y){
43     if(x==0||y==0)return 0; access(x); splay(x); rev[x]^=1; fa[x]=y; return 1;
44 }
45 int querysum(int x,int y){
46     if(x==0||y==0)return 0; if(x==y)return v[x]; access(x); int a=access(y); splay(x); 
47     if(x==a)return v[a]+sm[ch[a][1]];else return sm[x]+v[a]+sm[ch[a][1]];
48 }
49 void change(int x,int y){
50     splay(x); v[x]=y; update(x);
51 }
52 int find(int x){
53     access(x); splay(x); while(ch[x][0])x=ch[x][0]; return x;
54 }
55 int n,m; char s[20];
56 int main(){
57     //freopen("test.txt","r",stdin);
58     scanf("%d",&n); inc(i,1,n)scanf("%d",&v[i]),fa[i]=0,ch[i][0]=ch[i][1]=rev[i]=0,sm[i]=v[i]; scanf("%d",&m);
59     inc(i,1,m){
60         int a,b; scanf("%s%d%d",s,&a,&b); 
61         if(s[0]=='b'){if(find(a)==find(b))puts("no");else link(a,b),puts("yes");}
62         if(s[0]=='p')change(a,b);
63         if(s[0]=='e')if(find(a)!=find(b))puts("impossible");else printf("%d
",querysum(a,b));
64     }
65     return 0;
66 }      

20160420