Given a tree with N ( N<=100000 ) nodes. Each node has a interger value x_i ( |x_i|<=10000 ).
You have to apply Q ( Q<=100000 ) operations:
1. 1 a b : answer the maximum contiguous sum (maybe empty,will always larger than or equal to 0 ) from the path a->b ( inclusive ).
2. 2 a b c : change all value in the path a->b ( inclusive ) to c.
Input
first line consists one interger N.
next line consists N interger x_i.
next N-1 line , each consists two interger u,v , means that node u and node v are connected
next line consists 1 interger Q.
next Q line : 1 a b or 2 a b c .
Output
For each query, output one line the maximum contiguous sum.
Example
Input:
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
Output:
5
9
GSS系列最后一道题终于攻破
树链剖分可做,不过代码很长,280行.....
酝酿了这么久终于写了,以前一直不敢做,今天觉得是时候了
又认真看了一遍入门http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
用了一个下午的时间把它AC了,觉得很欣慰,竟然是一次AC,幸福来得太突然.....
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 const 2 inf=-maxlongint; 3 type 4 node=record 5 lson,rson,left,right,lmax,rmax,amax,lazy,sum:longint; 6 end; 7 8 var 9 tree:array[0..200010]of node; 10 first,next,last:array[0..200010]of longint; 11 son,fa,size,dep,w,top,root,a:array[0..100010]of longint; 12 flag:array[0..100010]of boolean; 13 tot,n,num,ll,rr:longint; 14 15 function max(x,y:longint):longint; 16 begin 17 if x>y then exit(x); 18 exit(y); 19 end; 20 21 procedure swap(var x,y:longint); 22 var 23 t:longint; 24 begin 25 t:=x;x:=y;y:=t; 26 end; 27 28 procedure insert(x,y:longint); 29 begin 30 inc(num); 31 last[num]:=y; 32 next[num]:=first[x]; 33 first[x]:=num; 34 end; 35 36 procedure dfs1(x,d,f:longint); 37 var 38 i,j:longint; 39 begin 40 fa[x]:=f; 41 flag[x]:=true; 42 dep[x]:=d; 43 size[x]:=1; 44 i:=first[x]; 45 j:=0; 46 while i<>0 do 47 begin 48 if flag[last[i]]=false then 49 begin 50 dfs1(last[i],d+1,x); 51 inc(size[x],size[last[i]]); 52 if size[last[i]]>size[j] then j:=last[i]; 53 end; 54 i:=next[i]; 55 end; 56 son[x]:=j; 57 end; 58 59 procedure build(l,r:longint); 60 var 61 now,mid:longint; 62 begin 63 inc(tot); 64 now:=tot; 65 with tree[now] do 66 begin 67 left:=l; 68 right:=r; 69 lazy:=inf; 70 end; 71 if l=r then exit; 72 mid:=(l+r)>>1; 73 with tree[now] do 74 begin 75 lson:=tot+1; 76 build(l,mid); 77 rson:=tot+1; 78 build(mid+1,r); 79 end; 80 end; 81 82 procedure new(x,now:longint); 83 begin 84 with tree[now] do 85 begin 86 if left<>right then lazy:=x; 87 sum:=x*(right-left+1); 88 amax:=max(0,sum); 89 lmax:=amax; 90 rmax:=amax; 91 end; 92 end; 93 94 procedure down(now:longint); 95 begin 96 with tree[now] do 97 begin 98 new(lazy,lson); 99 new(lazy,rson); 100 lazy:=inf; 101 end; 102 end; 103 104 procedure up(now:longint); 105 begin 106 with tree[now] do 107 begin 108 sum:=tree[lson].sum+tree[rson].sum; 109 amax:=max(max(tree[lson].amax,tree[rson].amax),tree[lson].rmax+tree[rson].lmax); 110 lmax:=max(tree[lson].lmax,tree[lson].sum+tree[rson].lmax); 111 rmax:=max(tree[rson].rmax,tree[rson].sum+tree[lson].rmax); 112 end; 113 end; 114 115 procedure change(x,now:longint); 116 var 117 mid:longint; 118 begin 119 with tree[now] do 120 begin 121 if(ll<=left)and(rr>=right) then 122 begin 123 new(x,now); 124 exit; 125 end; 126 if lazy<>inf then down(now); 127 mid:=(left+right)>>1; 128 if rr>mid then change(x,rson); 129 if ll<=mid then change(x,lson); 130 up(now); 131 end; 132 end; 133 134 procedure dfs2(x,t,ww:longint); 135 var 136 i:longint; 137 begin 138 flag[x]:=false; 139 top[x]:=t; 140 w[x]:=ww; 141 if son[x]=0 then 142 begin 143 root[x]:=tot+1; 144 build(1,ww); 145 ll:=ww; 146 rr:=ww; 147 change(a[x],root[x]); 148 exit; 149 end; 150 dfs2(son[x],t,ww+1); 151 root[x]:=root[son[x]]; 152 ll:=ww; 153 rr:=ww; 154 change(a[x],root[x]); 155 i:=first[x]; 156 while i<>0 do 157 begin 158 if flag[last[i]] then dfs2(last[i],last[i],1); 159 i:=next[i]; 160 end; 161 end; 162 163 procedure init; 164 var 165 i,x,y:longint; 166 begin 167 read(n); 168 for i:=1 to n do 169 read(a[i]); 170 for i:=1 to n-1 do 171 begin 172 read(x,y); 173 insert(x,y); 174 insert(y,x); 175 end; 176 dfs1(1,1,0); 177 dfs2(1,1,1); 178 end; 179 180 procedure get(var am,lm,rm,su:longint;now:longint); 181 var 182 mid:longint; 183 begin 184 with tree[now] do 185 begin 186 if lazy<>inf then down(now); 187 if(ll<=left)and(rr>=right) then 188 begin 189 am:=max(max(am,amax),lm+rmax); 190 lm:=max(lmax,sum+lm); 191 rm:=max(rm,su+rmax); 192 su:=su+sum; 193 exit; 194 end; 195 mid:=(left+right)>>1; 196 if rr>mid then get(am,lm,rm,su,rson); 197 if ll<=mid then get(am,lm,rm,su,lson); 198 end; 199 end; 200 201 procedure work1; 202 var 203 x,y,amax1,lmax1,rmax1,sum1,amax2,lmax2,rmax2,sum2:longint; 204 begin 205 read(x,y); 206 amax1:=0; 207 lmax1:=0; 208 rmax1:=0; 209 sum1:=0; 210 amax2:=0; 211 lmax2:=0; 212 rmax2:=0; 213 sum2:=0; 214 if dep[top[x]]<dep[top[y]] then swap(x,y); 215 while top[x]<>top[y] do 216 begin 217 ll:=1; 218 rr:=w[x]; 219 get(amax1,lmax1,rmax1,sum1,root[x]); 220 x:=fa[top[x]]; 221 if dep[top[x]]<dep[top[y]] then 222 begin 223 swap(x,y); 224 swap(amax1,amax2); 225 swap(lmax1,lmax2); 226 swap(rmax1,rmax2); 227 swap(sum1,sum2); 228 end; 229 end; 230 if dep[x]<dep[y] then 231 begin 232 swap(x,y); 233 swap(amax1,amax2); 234 swap(lmax1,lmax2); 235 swap(rmax1,rmax2); 236 swap(sum1,sum2); 237 end; 238 ll:=w[y]; 239 rr:=w[x]; 240 get(amax1,lmax1,rmax1,sum1,root[x]); 241 writeln(max(max(amax1,amax2),lmax1+lmax2)); 242 end; 243 244 procedure work2; 245 var 246 x,y,z:longint; 247 begin 248 read(x,y,z); 249 if dep[top[x]]<dep[top[y]] then swap(x,y); 250 while top[x]<>top[y] do 251 begin 252 ll:=1; 253 rr:=w[x]; 254 change(z,root[x]); 255 x:=fa[top[x]]; 256 if dep[top[x]]<dep[top[y]] then swap(x,y); 257 end; 258 if dep[x]<dep[y] then swap(x,y); 259 ll:=w[y]; 260 rr:=w[x]; 261 change(z,root[x]); 262 end; 263 264 procedure work; 265 var 266 i,q,s:longint; 267 begin 268 read(q); 269 for i:=1 to q do 270 begin 271 read(s); 272 if s=1 then work1 273 else work2; 274 end; 275 end; 276 277 begin 278 init; 279 work; 280 end.