樹的難題【樹的點分治】【線段樹(修改/查詢/合併)】
2020-08-12 07:36:10
本人最近遇到的一道特別好的題目，把此題本人的見解和做法分享出來作爲本蒟蒻的又一篇題解，有什麼缺點請大家指出，謝謝！（下面 下麪附有code）
題目描述
輸入格式
樣例輸入
8 4 3 4
-7 9 6 1
1 2 1
1 3 2
1 4 1
2 5 1
5 6 2
3 7 1
3 8 3
輸出格式
樣例輸出
11
數據範圍
題解
精簡版：
這種樹上亂七八糟的題顯然是要用樹的點分治的(￣▽￣)，找到當前的根，考慮到顏色段的存在，所以我們排序出邊顏色相同的放在一起(爲了判重*，在此前提下再把從根出發第一個到的點的編號相同的放在一起），(若有神犇有別的去重方法可以無視這句話) 然後不停查詢和維護兩顆線段樹（一顆儲存同色一顆儲存異色），每次更換顏色就合併兩顆線段樹；這樣即可統計答案。
詳細版：
先來想想樹的點分治大致怎麼解決問題：對於詢問樹上所有（區間）路徑，每次以當前樹的重心爲根，統計經過或包含這個根的所有路徑，統計（維護）答案，然後刪去這個根（打個標記等），接着分別處理它的每個子樹按照這個步驟繼續做下去，得到答案。這種做法實際時間複雜度其實是O(n logn），只是看上去大罷了。那麼這道題很明顯就可以用樹的點分治去做。
接下來再來想想這道題怎麼用樹的點分治呢…大致的模板還是不變的，問題在於怎麼去找到符合要求的路徑並且尋找答案。
先來解決第一個子問題：統計經過或包含當前根的長度 l 到 r 之間的路徑，這個可以從當前的根跑一邊BFS，找到每一條從當前根出發的長度在1-r之間的路徑，記錄下來這條路的深度，權值和，從根出發的第一條邊的顏色，從根出發第一個到的點的編號；這些以後統計答案都會用到。
接下來按照模板，對這些路進行排序，按照每條路從根出發的第一條邊的顏色爲第一關鍵字，從根出發第一個到的點的編號爲第二關鍵字從小到大排序（從大到小應該也沒有問題）(～￣▽￣)～
好的，接下來怎麼做呢？當然是統計答案了-(￣▽￣)- 可以去維護兩顆線段樹（下標爲經過邊的數量），一顆同色，一顆異色，每次從根出發第一個到的點編號不同時就把從當前位置到上一次的位置間的數放進同色線段樹中，然後每次遇到不同顏色時，合併兩顆線段樹即可，然後就可以直接線上段樹中按當前剩餘需要的邊數區間查詢答案。
*去重：解釋一下，因爲我用的方法是把所有經過當前根且不經過被刪掉的點的路找出來，所以會匹配時有不合法的情況，如下圖：
這樣就會出現走了重複的路，要進行判斷
貼一下code：
(打的還是古老的Pascal，並且有些長，重在理解，不喜勿噴)
var
bz:array[0..1000005]of boolean;
maxval,maxval2,jlbh,jlhm,c,f,l,map,maps,last,dis,b,cs,la,las,first,jlcs,jl,jlfs:array[0..1000005]of longint;
head,tail,sum,n,u,v,w,l2,r2,minn,mint,size,ans,m,root,i:longint;
procedure ins(x,y,z:longint);
begin
inc(sum);
map[sum]:=y;
maps[sum]:=z;
last[sum]:=l[x];
l[x]:=sum;
end;
function build(x,la:longint):longint; //建樹
var
i,bd,maxson:longint;
begin
i:=l[x];
f[x]:=1;
maxson:=0;
while i<>0 do
begin
if (bz[map[i]])and(map[i]<>la) then
begin
bd:=build(map[i],x);
if bd>maxson then
maxson:=bd;
f[x]:=f[x]+f[map[i]];
end;
i:=last[i];
end;
if size-maxson-1>maxson then maxson:=size-maxson-1;
if maxson<minn then
begin
minn:=maxson;
mint:=x;
end;
exit(f[x]);
end;
procedure pai(i,j:longint); //排序
var
l5,r5,mid,mid2,t:longint;
begin
l5:=i; r5:=j;
mid:=jlfs[(i+j)div 2];
mid2:=jlhm[(i+j)div 2];
while i<j do
begin
while (jlfs[i]<mid)or(jlfs[i]=mid)and(jlhm[i]<mid2) do inc(i);
while (jlfs[j]>mid)or(jlfs[j]=mid)and(jlhm[j]>mid2) do dec(j);
if i<=j then
begin
t:=jl[i]; jl[i]:=jl[j]; jl[j]:=t;
t:=jlfs[i]; jlfs[i]:=jlfs[j]; jlfs[j]:=t;
t:=jlcs[i]; jlcs[i]:=jlcs[j]; jlcs[j]:=t;
t:=jlhm[i]; jlhm[i]:=jlhm[j]; jlhm[j]:=t;
inc(i);
dec(j);
end;
end;
if i<r5 then pai(i,r5);
if l5<j then pai(l5,j);
end;
function max(a1,a2:longint):longint;
begin
if a1>a2 then
max:=a1
else
max:=a2;
end;
procedure insert(now,nl,nr,sd,qz:longint); //把值放進線段樹中
var
mid:longint;
begin
if nl=nr then
begin
if nl=sd then
begin
if qz>maxval2[now] then
maxval2[now]:=qz;
end;
exit;
end;
if (nl>sd)or(nr<sd) then exit;
mid:=(nl+nr)div 2;
insert(now*2,nl,mid,sd,qz);
insert(now*2+1,mid+1,nr,sd,qz);
maxval2[now]:=max(maxval2[now*2],maxval2[now*2+1]);
end;
function query(now,nl,nr,mbl,mbr:longint):longint; //在異色樹查詢答案
var
mid:longint;
begin
if (nl>=mbl)and(nr<=mbr) then
begin
exit(maxval[now]);
end;
if maxval[now]=-1000000000 then exit(-1000000000);
if (nl>mbr)or(nr<mbl) then exit(-1000000000);
mid:=(nl+nr)div 2;
query:=max(query(now*2,nl,mid,mbl,mbr),query(now*2+1,mid+1,nr,mbl,mbr));
end;
function query2(now,nl,nr,mbl,mbr:longint):longint; //在同色樹查詢答案
var
mid:longint;
begin
if (nl>=mbl)and(nr<=mbr) then
begin
exit(maxval2[now]);
end;
if maxval2[now]=-1000000000 then exit(-1000000000);
if (nl>mbr)or(nr<mbl) then exit(-1000000000);
mid:=(nl+nr)div 2;
query2:=max(query2(now*2,nl,mid,mbl,mbr),query2(now*2+1,mid+1,nr,mbl,mbr));
end;
procedure merge(now,nl,nr:longint); //合併兩顆線段樹歸爲異色樹
var
mid:longint;
begin
if nl=nr then
begin
if maxval[now]<maxval2[now] then maxval[now]:=maxval2[now];
maxval2[now]:=-1000000000;
exit;
end;
if maxval2[now]=-1000000000 then exit;
mid:=(nl+nr)div 2;
if maxval[now]<maxval2[now] then maxval[now]:=maxval2[now];
merge(now*2,nl,mid);
merge(now*2+1,mid+1,nr);
maxval2[now]:=-1000000000;
end;
procedure csh(now,nl,nr:longint); //初始化線段樹的值
var
mid:longint;
begin
if maxval[now]=-1000000000 then exit;
maxval2[now]:=-1000000000;
if nl=nr then
begin
if nl=0 then
maxval[now]:=0
else
maxval[now]:=-1000000000;
exit;
end;
mid:=(nl+nr)div 2;
csh(now*2,nl,mid);
csh(now*2+1,mid+1,nr);
maxval[now]:=max(maxval[now*2],maxval[now*2+1]);
end;
procedure find(x:longint); //尋找以當前點爲根的答案
var
i,l1,r1,s,sz,last2,j,fd:longint;
bj:boolean;
begin
head:=0;
tail:=1;
b[1]:=x;
dis[x]:=0; //記錄從根走到當前節點的路徑權值
cs[x]:=0; //記錄深度
la[1]:=0;
las[1]:=0;
jlbh[x]:=0; //記錄從根出發第一個到的點編號
first[x]:=0; //記錄從根出發第一次經過的邊的顏色
s:=0;
while head<tail do
begin
inc(head);
i:=l[b[head]];
while i<>0 do
begin
if (bz[map[i]])and(la[head]<>map[i]) then
begin
inc(tail);
b[tail]:=map[i];
la[tail]:=b[head];
if las[head]<>maps[i] then
dis[map[i]]:=dis[b[head]]+c[maps[i]]
else
dis[map[i]]:=dis[b[head]];
las[tail]:=maps[i];
first[map[i]]:=first[b[head]];
jlbh[map[i]]:=jlbh[b[head]];
if jlbh[map[i]]=0 then
jlbh[map[i]]:=map[i];
if first[map[i]]=0 then
first[map[i]]:=maps[i];
cs[map[i]]:=cs[b[head]]+1;
inc(s);
jl[s]:=dis[map[i]]; //記錄從根走到當前節點的路徑權值
jlfs[s]:=first[map[i]]; //記錄從根出發第一次經過的邊的顏色
jlcs[s]:=cs[map[i]]; //記錄深度
jlhm[s]:=jlbh[map[i]]; //記錄從根出發第一個到的點編號
end;
i:=last[i];
end;
end;
if s=0 then exit;
pai(1,s);
last2:=0;
csh(1,0,r2); //給樹賦上初值
bj:=false;
for i:=1 to s do
begin
if r2-jlcs[i]>=0 then
begin
fd:=query(1,0,r2,max(0,l2-jlcs[i]),max(0,r2-jlcs[i])); //查詢答案
if (jlfs[i]=jlfs[i-1])and(bj) then
fd:=max(fd,query2(1,0,r2,max(0,l2-jlcs[i]),max(0,r2-jlcs[i])))-c[jlfs[i]];
if (fd>-1000000000)and(fd+jl[i]>ans) then
ans:=fd+jl[i];
end;
if jlhm[i]<>jlhm[i+1] then
begin
bj:=true;
for j:=last2+1 to i do
if jlcs[j]<=r2 then
insert(1,0,r2,jlcs[j],jl[j]);//修改同色樹
last2:=i;
end;
if jlfs[i]<>jlfs[i+1] then
begin
merge(1,0,r2); //合併兩棵樹歸爲異色樹
bj:=false;
end;
end;
end;
procedure dg(x:longint); //點分治操作中心
var
i,root:longint;
begin
find(x);
bz[x]:=false;
i:=l[x];
while i<>0 do
begin
if bz[map[i]] then
begin
size:=f[map[i]];
minn:=maxlongint; mint:=0;
root:=build(map[i],0);
dg(mint);
end;
i:=last[i];
end;
end;
begin //主程式
assign(input,'journey.in');
reset(input);
assign(output,'journey.out');
rewrite(output);
readln(n,m,l2,r2);
for i:=1 to m do
begin
read(c[i]);
end;
for i:=1 to n do bz[i]:=true;
for i:=1 to n-1 do
begin
readln(u,v,w);
ins(u,v,w);
ins(v,u,w);
end;
ans:=-maxlongint;
randomize;
minn:=maxlongint; mint:=0;
size:=n;
root:=build(random(n)+1,0);
root:=build(mint,0);
dg(mint);
writeln(ans);
end.
謝謝大家觀看！