学步园

题意：

   求一棵树上一条长度为L~R之间的权值最大的路径，长度是这条路径上的边数，N<=100000，L<=R<=N

分析：

   直接树形dp难度较大，由于是求一条树中XX路径，容易想到树的分治（详见QZC论文）

算法

   这里讲一种基于点的分治，选树的重心为根，先算出经过自己的路径更新答案，再递归到子树

   顺序处理每个子树，先搜出这棵子树中长度为1~r的所有路径，用个数组存之前的每个深度的路径最大权值，拿当前这棵子树去“合”上句话那个数组，“合”完之后再用当前子树的信息区更新“那个数组”，“合”的过程相当于一次dp，即在两个线性表中取max{a[i]+b[j],l<=i+j<=r}，用单调队列实现。

   为了搞笑，我编了个线段数来“合”，为此盾哥赔了我10个鸡块，哈哈，线段树都1.5s过了（单调队列0.2s）

代码（线段树）：

{$M 10000000} {$inline on}<br /> program syj;<br /> uses math;<br /> const oo=maxlongint>>1;<br /> var i,x,y,z,ed,n,lc,rc,e,tot,minx,mi,ans,t:longint;<br /> h,qd,qs,son,si:array[1..100005]of longint;<br /> next,point,w,l,r,b,bb,ma:array[1..300005]of longint;<br /> v:array[1..100005]of boolean;<br /> procedure dfs1(i,fa,dep,s:longint); inline;<br /> var j,k:longint;<br /> begin<br /> if dep<=rc then begin<br /> inc(ed);qd[ed]:=dep;qs[ed]:=s;<br /> end;<br /> j:=h[i]; son[i]:=1;<br /> while j<>0 do begin<br /> k:=point[j];<br /> if (k<>fa)and not v[k] then begin<br /> dfs1(k,i,dep+1,s+w[j]);<br /> inc(son[i],son[k]);<br /> end;<br /> j:=next[j];<br /> end;<br /> end;<br /> procedure dfs2(i,fa:longint); inline;<br /> var j,k,mins:longint;<br /> begin<br /> mins:=tot-son[i]; j:=h[i];<br /> while j<>0 do begin<br /> k:=point[j];<br /> if (k<>fa)and not v[k] then begin<br /> dfs2(k,i);<br /> if son[k]>mins then mins:=son[k];<br /> end;<br /> j:=next[j];<br /> end;<br /> if mins<minx then begin<br /> minx:=mins;mi:=i;<br /> end;<br /> end;<br /> procedure maxi(var x:longint;y:longint); inline;<br /> begin<br /> if y>x then x:=y;<br /> end;<br /> procedure update(i,ll,rr,k:longint); inline;<br /> var mid:longint;<br /> begin<br /> if ll>rr then exit;<br /> if (l[i]=ll)and(r[i]=rr) then begin<br /> b[i]:=k;maxi(ma[i],k);exit;<br /> end;<br /> mid:=(l[i]+r[i])div 2;<br /> if bb[i]>-oo-1 then begin<br /> bb[i*2]:=bb[i];bb[i*2+1]:=bb[i];ma[i*2]:=bb[i];ma[i*2+1]:=bb[i];<br /> b[i]:=-oo-1;bb[i]:=-oo-1;<br /> end;<br /> if b[i]>-oo-1 then begin<br /> b[i*2]:=b[i];b[i*2+1]:=b[i];maxi(ma[i*2],b[i]);maxi(ma[i*2+1],b[i]);<br /> b[i]:=-oo-1;<br /> end;<br /> update(i*2,ll,min(mid,rr),k);update(i*2+1,max(mid+1,ll),rr,k);<br /> ma[i]:=max(ma[i*2],ma[i*2+1]);<br /> end;<br /> function ask(i,ll,rr:longint):longint; inline;<br /> var mid:longint;<br /> begin<br /> if ll>rr then exit(-oo);<br /> if (l[i]=ll)and(r[i]=rr) then exit(ma[i]);<br /> if bb[i]>-oo-1 then begin<br /> bb[i*2]:=bb[i];bb[i*2+1]:=bb[i];ma[i*2]:=bb[i];ma[i*2+1]:=bb[i];<br /> b[i]:=-oo-1;bb[i]:=-oo-1;<br /> end;<br /> if b[i]>-oo-1 then begin<br /> b[i*2]:=b[i];b[i*2+1]:=b[i];maxi(ma[i*2],b[i]);maxi(ma[i*2+1],b[i]);<br /> b[i]:=-oo-1;<br /> end;<br /> mid:=(l[i]+r[i])div 2;<br /> ask:=max(ask(i*2,ll,min(mid,rr)),ask(i*2+1,max(mid+1,ll),rr));<br /> end;<br /> procedure work(i:longint); inline;<br /> var j,k,ll:longint;<br /> begin<br /> v[i]:=true; j:=h[i]; ma[1]:=-oo;bb[1]:=-oo;b[1]:=-oo-1; update(1,0,0,0);<br /> while j<>0 do begin<br /> k:=point[j];<br /> if not v[k] then begin<br /> ed:=0;<br /> dfs1(k,0,1,w[j]);<br /> for ll:=1 to ed do maxi(ans,ask(1,max(0,lc-qd[ll]),rc-qd[ll])+qs[ll]);<br /> for ll:=1 to ed do update(1,qd[ll],qd[ll],qs[ll]);<br /> end;<br /> j:=next[j];<br /> end;<br /> j:=h[i];<br /> while j<>0 do begin<br /> k:=point[j];<br /> if not v[k] then begin<br /> minx:=n+1; tot:=son[k];<br /> dfs2(k,0);<br /> work(mi);<br /> end;<br /> j:=next[j];<br /> end;<br /> end;<br /> procedure build(i,ll,rr:longint); inline;<br /> var mid:longint;<br /> begin<br /> if ll>rr then exit;<br /> l[i]:=ll;r[i]:=rr;b[i]:=-oo-1;ma[i]:=-oo-1; mid:=(ll+rr)>>1;<br /> if ll=rr then exit;<br /> build(i*2,ll,mid);build(i*2+1,mid+1,rr);<br /> end;<br /> procedure link(x,y,z:longint);<br /> begin<br /> inc(e); next[e]:=h[x];point[e]:=y;w[e]:=z;h[x]:=e;<br /> end;<br /> begin<br /> assign(input,'wood.in');reset(input);<br /> assign(output,'wood.out');rewrite(output);<br /> readln(n,lc,rc);<br /> for i:=1 to n-1 do begin<br /> readln(x,y,z);link(x,y,z);link(y,x,z);<br /> end;<br /> ans:=-oo;<br /> build(1,0,n);<br /> work(1);<br /> writeln(ans);<br /> close(input);close(output);<br /> end.<br />

单调队列关键代码：

procedure deal(i:longint);var j,k,i1,i2,t:longint;<br /> begin<br /> k:=d[i];j:=p[k];o[i]:=true;t:=0;<br /> while k<>0 do begin<br /> if not o[j] then begin<br /> max:=0;dfs1(i,j,c[k],1);<br /> beg:=1;clo:=0;i2:=-1;<br /> for i1:=max downto 0 do begin<br /> for i2:=i2+1 to r-i1 do<br /> if i2<=t then begin<br /> while (beg<=clo)and(a[q[clo]]<=a[i2]) do dec(clo);<br /> inc(clo);q[clo]:=i2;<br /> end else break;<br /> while (beg<=clo)and(q[beg]+i1<l) do inc(beg);<br /> if (beg<=clo)and(a[q[beg]]+b[i1]>ans)<br /> then ans:=a[q[beg]]+b[i1];<br /> end;<br /> if max>t then for t:=t+1 to max do a[t]:=-(1<<29);<br /> for i1:=1 to max do<br /> if b[i1]>a[i1] then a[i1]:=b[i1];<br /> tot:=s[j];min:=maxlongint;<br /> dfs2(i,j);go[j]:=best;<br /> end;<br /> k:=next[k];j:=p[k];<br /> end;<br /> k:=d[i];j:=p[k];<br /> while k<>0 do begin<br /> if not o[j] and (s[j]>=l) then deal(go[j]);<br /> k:=next[k];j:=p[k];<br /> end;<br /> end;

可惜考试时被这个单调队列萎到了，盾哥出的题就是恶心

这题ms是wc一道题的简化版