題意：
給定N個節點要求維護森林：
b x y表示查詢x y的連通性 如果連通輸出"no"否則輸出"yes"并在x,y之間連邊
p x y表示將x節點權值修改為y
e x y表示查詢x到y路徑上的權值和 如果連通輸出答案否則輸出"impossible"
N<=30000 Q<=300000
做法：
要在線么..動態樹搞搞吧
對于B
查詢兩個節點是否在同一棵動態樹中 其實便是拉實后看根節點是否一樣
如果不連通 那么將其中一個節點變成所在動態樹的根 然后接到另一個節點上去
對于P 沒什么好說的 別忘了update
對于E 也沒什么好說的 兩次拉實就可以了 找到LCA然后查詢
1 #include <cstdio>
2 struct Tsplay
3 {
4 #define Lch(t) (T[t].l)
5 #define Rch(t) (T[t].r)
6 #define Par(t) (T[t].p)
7 #define Sum(t) (T[t].sum)
8 #define Val(t) (T[t].val)
9 #define Rev(t) (T[t].rev)
10 #define Root(t) (Lch(Par(t))!=t&&Rch(Par(t))!=t)
11 int l,r,p;
12 int sum,val;
13 bool rev;
14 } T[30005];
15 int Stk[30005],N,Q,x,y;
16 char cmd[1005];
17 inline void Down(int x)
18 {
19 if (Rev(x))
20 {
21 int t=Lch(x);Lch(x)=Rch(x);Rch(x)=t;
22 Rev(Lch(x))^=1,Rev(Rch(x))^=1,Rev(x)=0;
23 }
24 }
25 inline void Tupdate(int x)
26 {
27 Sum(x)=Sum(Lch(x))+Val(x)+Sum(Rch(x));
28 }
29 inline void zig(int x)
30 {
31 int y=Par(x),z=Par(y);
32 Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
33 if (Lch(z)==y) Lch(z)=x;
34 else
35 if (Rch(z)==y) Rch(z)=x;
36 Par(x)=z,Par(y)=x;
37 Tupdate(y);
38 }
39 inline void zag(int x)
40 {
41 int y=Par(x),z=Par(y);
42 Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
43 if (Lch(z)==y) Lch(z)=x;
44 else
45 if (Rch(z)==y) Rch(z)=x;
46 Par(x)=z,Par(y)=x;
47 Tupdate(y);
48 }
49 inline void splay(int x)
50 {
51 Stk[++Stk[0]]=x;
52 for (int u=x;!Root(u);u=Par(u))
53 Stk[++Stk[0]]=Par(u);
54 for (;Stk[0];--Stk[0])
55 Down(Stk[Stk[0]]);
56 for (int y,z;!Root(x);)
57 {
58 y=Par(x),z=Par(y);
59 if (Root(y))
60 if (Lch(y)==x) zig(x);
61 else zag(x);
62 else
63 if (Lch(z)==y)
64 if (Lch(y)==x) zig(y),zig(x);
65 else zag(x),zig(x);
66 else
67 if (Rch(y)==x) zag(y),zag(x);
68 else zig(x),zag(x);
69 }
70 Tupdate(x);
71 }
72 inline int Expose(int u)
73 {
74 int v=0;
75 for (;u;u=Par(u))
76 splay(u),Rch(u)=v,Tupdate(v=u);
77 for (;Lch(v);v=Lch(v));
78 return v;
79 }
80 inline void Modify(int x,int y)
81 {
82 splay(x),Val(x)=y,Tupdate(x);
83 }
84 inline void Query(int x,int y)
85 {
86 int Ry=Expose(y),Rx=Expose(x);
87 if (Rx!=Ry) puts("impossible");
88 else
89 for (int u=y,v=0;u;u=Par(u))
90 {
91 if (splay(u),!Par(u))
92 {
93 printf("%d\n",Sum(Rch(u))+Val(u)+Sum(v));
94 return;
95 }
96 Rch(u)=v,Tupdate(v=u);
97 }
98 }
99 inline void Connect(int x,int y)
100 {
101 int Ry=Expose(y),Rx=Expose(x);
102 if (Rx==Ry) puts("no");
103 else
104 {
105 splay(x);
106 Rch(x)=0,Rev(x)=1,Par(x)=y;
107 puts("yes");
108 }
109 }
110 int main()
111 {
112 freopen("otoci.in","r",stdin);
113 freopen("otoci.out","w",stdout);
114 scanf("%d",&N);
115 for (int i=1;i<=N;++i)
116 scanf("%d",&Val(i)),Sum(i)=Val(i);
117 for (scanf("%d",&Q);Q--;)
118 {
119 scanf("%s%d%d",cmd,&x,&y);
120 if (cmd[0]=='e') Query(x,y);
121 else
122 if (cmd[0]=='b') Connect(x,y);
123 else Modify(x,y);
124 }
125 return 0;
126 }
127
128