5 1 2 2 4 2 5 1 3 1 2 3 4 5 6 4 2 3 2 1 2 4 2 3 1 3 5 3 2 1 4 4 1 4
3 -1 7
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 300010; 4 struct arc { 5 int to,next; 6 arc(int x = 0,int y = -1) { 7 to = x; 8 next = y; 9 } 10 } e[maxn<<1]; 11 int head[maxn],tot; 12 void add(int u,int v) { 13 e[tot] = arc(v,head[u]); 14 head[u] = tot++; 15 } 16 struct LCT { 17 int fa[maxn],ch[maxn][2],parent[maxn]; 18 int add[maxn],flip[maxn],maxv[maxn],key[maxn]; 19 void init() { 20 memset(ch,0,sizeof ch); 21 memset(fa,0,sizeof fa); 22 flip[0] = flip[1] = 0; 23 add[0] = add[1] = 0; 24 parent[0] = parent[1] = 0; 25 key[0] = maxv[0] = 0; 26 } 27 inline void pushup(int x) { 28 maxv[x] = max(key[x],max(maxv[ch[x][0]],maxv[ch[x][1]])); 29 } 30 inline void inc(int x,int val) { 31 if(!x) return; 32 add[x] += val; 33 key[x] += val; 34 maxv[x] += val; 35 } 36 inline void pushdown(int x) { 37 if(add[x]) { 38 inc(ch[x][0],add[x]); 39 inc(ch[x][1],add[x]); 40 add[x] = 0; 41 } 42 if(flip[x]) { 43 flip[ch[x][0]] ^= 1; 44 flip[ch[x][1]] ^= 1; 45 swap(ch[x][0],ch[x][1]); 46 flip[x] = 0; 47 } 48 } 49 void rotate(int x,int kd) { 50 int y = fa[x]; 51 pushdown(y); 52 pushdown(x); 53 ch[y][kd^1] = ch[x][kd]; 54 fa[ch[x][kd]] = y; 55 fa[x] = fa[y]; 56 ch[x][kd] = y; 57 fa[y] = x; 58 if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x; 59 pushup(y); 60 } 61 void splay(int x,int goal = 0) { 62 int y = x; 63 pushdown(x); 64 while(fa[y]) y = fa[y]; 65 if(x != y) { 66 parent[x] = parent[y]; 67 parent[y] = 0; 68 while(fa[x] != goal) { 69 pushdown(fa[fa[x]]); 70 pushdown(fa[x]); 71 pushdown(x); 72 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]); 73 else{ 74 int y = fa[x],z = fa[y],s = (ch[z][0] == y); 75 if(x == ch[y][s]){ 76 rotate(x,s^1); 77 rotate(x,s); 78 }else{ 79 rotate(y,s); 80 rotate(x,s); 81 } 82 } 83 } 84 } 85 pushup(x); 86 } 87 void access(int x){ 88 for(int y = 0; x; x = parent[x]){ 89 splay(x); 90 fa[ch[x][1]] = 0; 91 parent[ch[x][1]] = x; 92 ch[x][1] = y; 93 fa[y] = x; 94 parent[y] = 0; 95 y = x; 96 pushup(x); 97 } 98 } 99 void makeroot(int x){ 100 access(x); 101 splay(x); 102 flip[x] ^= 1; 103 } 104 void join(int x,int y){ 105 makeroot(x); 106 makeroot(y); 107 parent[x] = y; 108 } 109 int GetRoot(int x){ 110 access(x); 111 splay(x); 112 while(ch[x][0]) x = ch[x][0]; 113 return x; 114 } 115 void cut(int x){ 116 access(x); 117 splay(x); 118 fa[ch[x][0]] = 0; 119 parent[ch[x][0]] = parent[x]; 120 ch[x][0] = 0; 121 parent[x] = 0; 122 pushup(x); 123 } 124 void update(int x,int y,int val){ 125 access(y); 126 for(y = 0; x; x = parent[x]){ 127 splay(x); 128 if(!parent[x]){ 129 inc(ch[x][1],val); 130 inc(y,val); 131 key[x] += val; 132 return; 133 } 134 fa[ch[x][1]] = 0; 135 parent[ch[x][1]] = x; 136 ch[x][1] = y; 137 fa[y] = x; 138 parent[y] = 0; 139 y = x; 140 pushup(x); 141 } 142 } 143 int query(int x,int y){ 144 access(y); 145 for(y = 0; x; x = parent[x]){ 146 splay(x); 147 if(!parent[x]) return max(max(maxv[ch[x][1]],maxv[y]),key[x]); 148 fa[ch[x][1]] = 0; 149 parent[ch[x][1]] = x; 150 ch[x][1] = y; 151 fa[y] = x; 152 parent[y] = 0; 153 y = x; 154 pushup(x); 155 } 156 return -1; 157 } 158 }lct; 159 void dfs(int u,int fa){ 160 for(int i = head[u]; ~i; i = e[i].next){ 161 if(e[i].to == fa) continue; 162 lct.parent[e[i].to] = u; 163 lct.add[e[i].to] = 0; 164 lct.flip[e[i].to] = 0; 165 dfs(e[i].to,u); 166 } 167 } 168 int main() { 169 int n,m,u,v,op,x,y,z; 170 while(~scanf("%d",&n)){ 171 memset(head,-1,sizeof head); 172 tot = 0; 173 lct.init(); 174 for(int i = 1; i < n; ++i){ 175 scanf("%d%d",&u,&v); 176 add(u,v); 177 add(v,u); 178 } 179 dfs(1,1); 180 for(int i = 1; i <= n; ++i) 181 scanf("%d",&lct.key[i]); 182 scanf("%d",&m); 183 while(m--){ 184 scanf("%d",&op); 185 if(op == 1){ 186 scanf("%d%d",&x,&y); 187 if(lct.GetRoot(x) == lct.GetRoot(y)) puts("-1"); 188 else lct.join(x,y); 189 }else if(op == 2){ 190 scanf("%d%d",&x,&y); 191 if(x == y || lct.GetRoot(x) != lct.GetRoot(y)) puts("-1"); 192 else{ 193 lct.makeroot(x); 194 lct.cut(y); 195 } 196 }else if(op == 3){ 197 scanf("%d%d%d",&z,&x,&y); 198 if(lct.GetRoot(x) != lct.GetRoot(y)) puts("-1"); 199 else lct.update(x,y,z); 200 }else if(op == 4){ 201 scanf("%d%d",&x,&y); 202 if(lct.GetRoot(x) != lct.GetRoot(y)) puts("-1"); 203 else printf("%d\n",lct.query(x,y)); 204 } 205 } 206 putchar(‘\n‘); 207 } 208 return 0; 209 }
原文:http://www.cnblogs.com/crackpotisback/p/4886253.html