Problem Query on The Trees
题目大意
给一棵树，有点权，要求维护4种操作。
操作1：加一条边。
操作2：删一条边。
操作3：将一条路径上的点权增加w。
操作4：询问一条路径上的点权最大值。
解题分析
lct练习题
ps：lct模板抄自黄学长。
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 300008 19 #define M 50008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31 32 int val[N],c[N][2],fa[N],mx[N],tag[N],rev[N],lt[N],st[N]; 33 int n,q,sum; 34 struct line{ 35 int u,v,nt; 36 }eg[N*2]; 37 void addedge(int u,int v){ 38 eg[++sum]=(line){u,v,lt[u]}; 39 lt[u]=sum; 40 } 41 void init(){ 42 rep(i,1,n) val[i]=c[i][0]=c[i][1]=mx[i]=tag[i]=rev[i]=lt[i]=fa[i]=0; 43 sum=1; 44 } 45 void dfs(int u){ 46 for (int i=lt[u];i;i=eg[i].nt){ 47 int v=eg[i].v; 48 if (fa[v] || v==1) continue; 49 fa[v]=u; 50 dfs(v); 51 } 52 } 53 bool isroot(int k){ 54 return c[fa[k]][0]!=k && c[fa[k]][1]!=k; 55 } 56 void pushup(int x){ 57 int l=c[x][0],r=c[x][1]; 58 mx[x]=max(max(mx[l],mx[r]),val[x]); 59 } 60 void pushdown(int x){ 61 int l=c[x][0],r=c[x][1]; 62 if (rev[x]){ 63 if (l) rev[l]^=1; 64 if (r) rev[r]^=1; 65 rev[x]^=1; 66 swap(c[x][0],c[x][1]); 67 } 68 if (tag[x]){ 69 if (l) {tag[l]+=tag[x]; mx[l]+=tag[x], val[l]+=tag[x]; } 70 if (r) {tag[r]+=tag[x]; mx[r]+=tag[x], val[r]+=tag[x]; } 71 tag[x]=0; 72 } 73 } 74 void rotate(int x){ 75 int y=fa[x],z=fa[y],l,r; 76 if (c[y][0]==x) l=0; else l=1; r=l^1; 77 if (!isroot(y)){ 78 if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; 79 } 80 fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 81 c[y][l]=c[x][r]; c[x][r]=y; 82 pushup(y); pushup(x); 83 } 84 void splay(int x){ 85 int top=0; st[++top]=x; 86 for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; 87 while (top) pushdown(st[top--]); 88 while (!isroot(x)){ 89 int y=fa[x],z=fa[y]; 90 if (!isroot(y)){ 91 if (c[y][0]==x^c[z][0]==y) rotate(x); 92 else rotate(y); 93 } 94 rotate(x); 95 } 96 } 97 void access(int x){ 98 int t=0; 99 while (x){ 100 splay(x); 101 c[x][1]=t; 102 pushup(x); 103 t=x; x=fa[x]; 104 } 105 } 106 int find(int u){ 107 access(u); splay(u); 108 while (c[u][0]) u=c[u][0]; 109 return u; 110 } 111 bool judge(int u,int v){ 112 return find(u)==find(v); 113 } 114 void rever(int u){ 115 access(u); splay(u); rev[u]^=1; 116 } 117 void link(int u,int v){ 118 rever(u); fa[u]=v; 119 } 120 void cut(int u,int v){ 121 rever(u); access(v); splay(v); fa[c[v][0]]=0; c[v][0]=0; pushup(v); 122 } 123 void add(int u,int v,int w){ 124 rever(u); access(v); splay(v); tag[v]+=w; mx[v]+=w; val[v]+=w; 125 } 126 void query(int u,int v){ 127 rever(u); access(v); splay(v); printf("%d ",mx[v]); 128 } 129 int main(){ 130 while (~scanf("%d",&n)) 131 { 132 init(); 133 rep(i,1,n-1){ 134 int u,v; 135 scanf("%d%d",&u,&v); 136 addedge(u,v); addedge(v,u); 137 } 138 rep(i,1,n){ 139 int x; 140 scanf("%d",&x); 141 val[i]=mx[i]=x; 142 } 143 dfs(1); 144 scanf("%d",&q); 145 while (q--){ 146 int x,u,v,w; 147 scanf("%d",&x); 148 if (x==1){ 149 scanf("%d %d",&u,&v); 150 if (!judge(u,v)) link(u,v); else puts("-1"); 151 } 152 if (x==2){ 153 scanf("%d %d",&u,&v); 154 if (judge(u,v) && u!=v) cut(u,v); else puts("-1"); 155 } 156 if (x==3){ 157 scanf("%d %d %d",&w,&u,&v); 158 if (judge(u,v)) add(u,v,w); else puts("-1"); 159 } 160 if (x==4){ 161 scanf("%d %d",&u,&v); 162 if (judge(u,v)) query(u,v); else puts("-1"); 163 } 164 } 165 printf(" "); 166 } 167 }