bzoj2282

到路径的距离就是到路径上的点最近的距离
首先看到最大值最小不难想到二分答案
下面的问题就是怎么判断，显然我们是不能穷举路径的
我们要找出消防路径的性质
仔细研究就会发现消防路径一定是树的直径的一段，这样必然最右
证明很简单，我们可以利用反证法解决，通过证明可以发现这个直径随便选一条就可以了
我们把树的直径拎出来，把直径上的点挂在直径下面（就相当于晾衣服一样……）
然后我们可以算出直径上每个点i的子树到i的最大距离，然后就很好处理了

 type node=record

        po,dis,next:longint;

      end;

 var q,d1,d2,p1,p2,p,f:array[..] of longint;

     e:array[..] of node;

     v:array[..] of boolean;

     t,n,m,s,l,r,i,x,y,z,len,w:longint;

 function max(a,b:longint):longint;

   begin

     if a>b then exit(a) else exit(b);

   end;

 procedure add(x,y,z:longint);

   begin

     inc(len);

     e[len].po:=y;

     e[len].dis:=z;

     e[len].next:=p[x];

     p[x]:=len;

   end;

 procedure dfs(x:longint);

   var i,y:longint;

   begin

     v[x]:=true;

     i:=p[x];

     while i<> do

     begin

       y:=e[i].po;

       if not v[y] then

       begin

         dfs(y);

         if d1[y]+e[i].dis>d1[x] then

         begin

           d2[x]:=d1[x];

           p2[x]:=p1[x]; //p1,p2记录的是这棵子树最长次长延伸的方向

           d1[x]:=d1[y]+e[i].dis;

           p1[x]:=i;

         end

         else if d1[y]+e[i].dis>d2[x] then

         begin

           d2[x]:=d1[y]+e[i].dis;

           p2[x]:=i;

         end;

       end;

       i:=e[i].next;

     end;

     if d1[x]+d2[x]>d1[w]+d2[w] then w:=x;

   end;

 procedure dfss(x:longint);

   var i,y:longint;

   begin

     i:=p[x];

     v[x]:=true;

     while i<> do

     begin

       y:=e[i].po;

       if not v[y] then

       begin

         dfss(y);

         f[x]:=max(f[x],f[y]+e[i].dis);

       end;

       i:=e[i].next;

     end;

   end;

 procedure getl(x:longint);

   begin

     if p1[x]<> then getl(e[p1[x]].po);

     inc(t); q[t]:=x; v[x]:=true;

   end;

 function check(len:longint):boolean;

   var l,r,w:longint;

   begin

     l:=;

     r:=t;

     w:=f[q[]];

     while (l<t) and (w+d1[q[l+]]<=len) do  //在满足最长距离不超过len的情况下使路径尽可能短

     begin

       inc(l);

       w:=max(w,f[q[l]]-d1[q[l]]);

     end;

     w:=f[q[t]]+d1[q[t]];

     while (r>l) and (w-d1[q[r-]]<=len) do

     begin

       dec(r);

       w:=max(w,f[q[r]]+d1[q[r]]);

     end;

     if d1[q[r]]-d1[q[l]]<=s then exit(true)

     else exit(false);

   end;

 begin

   readln(n,s);

   for i:= to n- do

   begin

     readln(x,y,z);

     add(x,y,z);

     add(y,x,z);

   end;

   dfs();

   fillchar(v,sizeof(v),false);

   getl(w);

   x:=w; i:=p2[x];

   while i<> do

   begin

     y:=e[i].po;

     inc(t); q[t]:=e[i].po; v[y]:=true;

     d1[y]:=d1[x]+e[i].dis;  //把直径提出来作为一条链，d1相当于到链头的距离

     i:=p1[y]; x:=y;

   end;

   r:=d1[x];

   for i:= to t do

   begin

     x:=q[i];

     dfss(x);

     l:=max(l,f[x]); //f处理的是子树最深距离

   end;

   if s<d1[q[t]] then

   begin

     while l<=r do

     begin

       m:=(l+r) shr ;

       if check(m) then r:=m-

       else l:=m+;

     end;

   end;

   writeln(l);

 end.

巴特西

bzoj2282

最新文章

热门文章