這是一道無比繁瑣的題目
話說這道題使我第一次練dfs序，比較感動；
首先dfs序就是在dfs過程中按照訪問的順序給每個點標上兩個“時間戳”
一個是第一次訪問到點i時的時間戳c[i]，一個是訪問完以i為根時的時間戳cc[i]
根據c[i]，我們就可以將樹變成序列，并且以i為根的子樹，是序列上連續的一段
當進行單點修改時，我們可以用樹狀數組前綴和維護樹上的點到根路徑上所有點的修改情況和；
比如當點i修改時（比如+1）?則w[c[i]]+1,w[cc[i]]-1
然后這道題顯然是要在dfs序上套帶修改的主席樹，根據bzoj2588的經驗我們很好解決這個問題
由于修改的點要離散化，已經離線了，干脆用lca-tarjan求lca好了
由于空間卡的比較嚴，所以我們不能直接樹狀數組+主席樹
而要先把原樹建成主席樹，然后修改的時候新建一棵主席樹，用樹狀數組+主席樹解決

1 const maxn=80001; 2 3 type node=record 4 po,next:longint; 5 end; 6 link=record 7 l,r,s:longint; 8 end; 9 point=record 10 x,y,z:longint; 11 end; 12 qu=record 13 num,loc,next:longint; 14 end; 15 16 17 var tree:array[0..10000010] of link; 18 q:array[0..80010] of point; 19 w:array[0..160010] of node; 20 que:array[0..160010] of qu; 21 v:array[0..80010] of boolean; 22 e:array[0..4] of longint; 23 g,fa,an,loc,d1,d2,ph,h,cc,c,b:array[0..80010] of longint; 24 st:array[0..80010,0..4] of longint; 25 sa,a:array[0..160010] of longint; 26 j,k,t,tot,num,len,x,y,z,i,p,s,n,m:longint; 27 28 function lowbit(x:longint):longint; 29 begin 30 exit(x and (-x)); 31 end; 32 33 procedure update(x:longint); 34 begin 35 tree[x].s:=tree[tree[x].l].s+tree[tree[x].r].s; 36 end; 37 38 procedure add(x,y:longint); 39 begin 40 inc(len); 41 w[len].po:=y; 42 w[len].next:=d1[x]; 43 d1[x]:=len; 44 end; 45 46 procedure addq(x,y,z:longint); 47 begin 48 inc(num); 49 que[num].num:=y; 50 que[num].loc:=z; 51 que[num].next:=d2[x]; 52 d2[x]:=num; 53 end; 54 55 function find(x:longint):longint; 56 var l,r,m:longint; 57 begin 58 l:=1; 59 r:=p; 60 while l<=r do 61 begin 62 m:=(l+r) shr 1; 63 if sa[m]=x then exit(m); 64 if sa[m]>x then r:=m-1 else l:=m+1; 65 end; 66 end; 67 68 function getf(x:longint):longint; 69 begin 70 if a[x]<>x then a[x]:=getf(a[x]); 71 exit(a[x]); 72 end; 73 74 procedure dfs(x:longint); 75 var i,y:longint; 76 begin 77 i:=d1[x]; 78 v[x]:=true; 79 inc(tot); 80 b[tot]:=x; //b表示序列上的點對應的樹上的哪個點 81 c[x]:=tot; 82 while i<>0 do 83 begin 84 y:=w[i].po; 85 if not v[y] then 86 begin 87 fa[y]:=x; 88 dfs(y); 89 a[y]:=x; 90 end; 91 i:=w[i].next; 92 end; 93 cc[x]:=tot; 94 i:=d2[x]; 95 while i<>0 do 96 begin 97 y:=que[i].num; 98 if v[y] and (an[que[i].loc]=0) then //lca-tarjan 99 an[que[i].loc]:=getf(y); 100 i:=que[i].next; 101 end; 102 end; 103 104 procedure sort(l,r: longint); 105 var i,j,x,y: longint; 106 begin 107 i:=l; 108 j:=r; 109 x:=a[(l+r) div 2]; 110 repeat 111 while a[i]<x do inc(i); 112 while x<a[j] do dec(j); 113 if not(i>j) then 114 begin 115 y:=a[i]; 116 a[i]:=a[j]; 117 a[j]:=y; 118 inc(i); 119 j:=j-1; 120 end; 121 until i>j; 122 if l<j then sort(l,j); 123 if i<r then sort(i,r); 124 end; 125 126 function build(l,r:longint):longint; 127 var m,q:longint; 128 begin 129 inc(t); 130 if l=r then exit(t) 131 else begin 132 q:=t; 133 m:=(l+r) shr 1; 134 tree[q].l:=build(l,m); 135 tree[q].r:=build(m+1,r); 136 exit(q); 137 end; 138 end; 139 140 function insert(last,x,l,r,z:longint):longint; 141 var m,q:longint; 142 begin 143 inc(t); 144 if l=r then 145 begin 146 tree[t].s:=tree[last].s+z; 147 exit(t); 148 end 149 else begin 150 m:=(l+r) shr 1; 151 q:=t; 152 if x<=m then 153 begin 154 tree[q].r:=tree[last].r; 155 last:=tree[last].l; 156 tree[q].l:=insert(last,x,l,m,z); 157 end 158 else begin 159 tree[q].l:=tree[last].l; 160 last:=tree[last].r; 161 tree[q].r:=insert(last,x,m+1,r,z); 162 end; 163 update(q); 164 exit(q); 165 end; 166 end; 167 168 procedure work(i,x,z:longint); 169 begin 170 while i<=n do //樹狀數組+主席樹 171 begin 172 h[i]:=insert(h[i],x,1,p,z); 173 i:=i+lowbit(i); 174 end; 175 end; 176 177 procedure get(x,y:longint); 178 var i:longint; 179 begin 180 e[y]:=1; 181 st[1,y]:=ph[x]; 182 i:=x; 183 while i>0 do 184 begin 185 if h[i]<>0 then 186 begin 187 inc(e[y]); 188 st[e[y],y]:=h[i]; 189 end; 190 i:=i-lowbit(i); 191 end; 192 end; 193 194 function sum:longint; 195 var i,j:longint; 196 begin 197 sum:=0; 198 for j:=1 to 4 do 199 for i:=1 to e[j] do 200 if (j<=2) then 201 sum:=sum+tree[tree[st[i,j]].r].s 202 else sum:=sum-tree[tree[st[i,j]].r].s;//u,v路徑上的情況為tree[u]+tree[v]-tree[lca(u,v)]-tree[fa[lca(u,v)]]; 203 end; 204 205 function getans(l,r,k:longint):longint; 206 var m,s,i,j:longint; 207 begin 208 if l=r then exit(sa[l]) 209 else begin 210 m:=(l+r) shr 1; 211 s:=sum; 212 if s>=k then 213 begin 214 for j:=1 to 4 do 215 for i:=1 to e[j] do 216 st[i,j]:=tree[st[i,j]].r; 217 exit(getans(m+1,r,k)); 218 end 219 else begin 220 k:=k-s; 221 for j:=1 to 4 do 222 for i:=1 to e[j] do 223 st[i,j]:=tree[st[i,j]].l; 224 exit(getans(l,m,k)); 225 end; 226 end; 227 end; 228 229 begin 230 readln(n,m); 231 for i:=1 to n do 232 begin 233 read(g[i]); 234 a[i]:=g[i]; 235 end; 236 s:=n; 237 for i:=1 to n-1 do 238 begin 239 readln(x,y); 240 add(x,y); 241 add(y,x); 242 end; 243 244 for i:=1 to m do 245 begin 246 readln(q[i].z,q[i].x,q[i].y); 247 if q[i].z=0 then 248 begin 249 inc(s); 250 a[s]:=q[i].y; 251 end 252 else begin 253 addq(q[i].x,q[i].y,i); 254 addq(q[i].y,q[i].x,i); 255 end; 256 end; 257 sort(1,s); 258 p:=1; 259 sa[1]:=a[1]; 260 for i:=2 to s do 261 if a[i]<>a[i-1] then //離散化 262 begin 263 inc(p); 264 sa[p]:=a[i]; 265 end; 266 267 for i:=1 to n do 268 a[i]:=i; 269 dfs(1); 270 t:=0; 271 h[0]:=build(1,p); 272 ph[0]:=h[0]; 273 for i:=1 to n do 274 begin 275 loc[i]:=find(g[b[i]]); 276 y:=fa[b[i]]; 277 ph[i]:=insert(ph[c[y]],loc[i],1,p,1); //建立未修改前的主席樹 278 end; 279 for i:=1 to m do 280 begin 281 if q[i].z<>0 then 282 begin 283 z:=an[i]; 284 get(c[q[i].x],1); //提取區間 285 get(c[q[i].y],2); 286 get(c[z],3); 287 get(c[fa[z]],4); 288 s:=0; 289 for j:=1 to 4 do 290 begin 291 for k:=1 to e[j] do 292 if (j<=2) then 293 s:=s+tree[st[k,j]].s 294 else s:=s-tree[st[k,j]].s; 295 end; 296 if s<q[i].z then writeln('invalid request!') 297 else writeln(getans(1,p,q[i].z)); 298 end 299 else begin 300 x:=q[i].x; 301 work(c[x],loc[c[x]],-1); 302 work(cc[x]+1,loc[c[x]],1); 303 loc[c[x]]:=find(q[i].y); 304 work(c[x],loc[c[x]],1); 305 work(cc[x]+1,loc[c[x]],-1); 306 end; 307 end; 308 end. View Code

?

轉載于:https://www.cnblogs.com/phile/p/4473091.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的bzoj1146的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。