【51NOD1766】树上的最远点对（线段树，LCA，RMQ）

题意：n个点被n-1条边连接成了一颗树，给出a~b和c~d两个区间，

表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j) |a<=i<=b,c<=j<=d｝

n<=100000 len[i]<=100000

思路：两年前张老师出的模拟赛里的题

设区间[a,b]中最大距离点对为[x1,y1]

[c,d]为[x2,y2]

则两区间各取一个点的最值只有两两组合4种可能

而线段树中pushup有6种，可以在同一个区间中取两点

求LCA需要LCA转RMQ O(1)做倍增或剖的话都会T

然并卵 P的常数太大了早日转C保平安

 type arr=record

           a,b:longint;

          end;

 var f,g:array[..,..]of longint;

     t:array[..]of arr;

     a,b,st,dep,dis,head,vet,next,len:array[..]of longint;

     n,m,i,tot,x,y,z,ans,time,que,j,x1,y1,x2,y2,tmp,tx,ty:longint;

     p,q:arr;

 procedure add(a,b,c:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  len[tot]:=c;

  head[a]:=tot;

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 procedure dfs(u,fa:longint);

 var e,v:longint;

 begin

  inc(time); st[u]:=time; a[time]:=dep[u]; b[time]:=u;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    dep[v]:=dep[u]+;

    dis[v]:=dis[u]+len[e];

    dfs(v,u);

    inc(time); a[time]:=dep[u]; b[time]:=u;

   end;

   e:=next[e];

  end;

 end;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function lca(x,y:longint):longint;

 var len,l,x1,y1:longint;

 begin

  x1:=st[x]; y1:=st[y];

  if x1>y1 then begin x1:=st[y]; y1:=st[x]; end;

  len:=y1-x1+;

  l:=trunc(ln(len)/ln());

  if f[x1,l]<f[y1-(<<l)+,l] then exit(g[x1,l])

   else exit(g[y1-(<<l)+,l]);

 end;

 function clac(x,y:longint):longint;

 var q:longint;

 begin

  q:=lca(x,y);

  exit(dis[x]+dis[y]-*dis[q]);

 end;

 function pushup(x,y:arr):arr;

 var t:arr;

 begin

  t:=x;

  if clac(y.a,y.b)>clac(t.a,t.b) then t:=y;

  if clac(x.a,y.a)>clac(t.a,t.b) then

  begin

   t.a:=x.a; t.b:=y.a;

  end;

  if clac(x.a,y.b)>clac(t.a,t.b) then

  begin

   t.a:=x.a; t.b:=y.b;

  end;

  if clac(x.b,y.a)>clac(t.a,t.b) then

  begin

   t.a:=x.b; t.b:=y.a;

  end;

  if clac(x.b,y.b)>clac(t.a,t.b) then

  begin

   t.a:=x.b; t.b:=y.b;

  end;

  exit(t);

 end;

 procedure build(l,r,p:longint);

 var mid:longint;

 begin

  if l=r then

  begin

   t[p].a:=l; t[p].b:=l;

   exit;

  end;

  mid:=(l+r)>>;

  build(l,mid,p<<);

  build(mid+,r,p<<+);

  t[p]:=pushup(t[p<<],t[p<<+]);

 end;

 function query(l,r,x,y,p:longint):arr;

 var mid:longint;

 begin

  if (l>=x)and(r<=y) then exit(t[p]);

  mid:=(l+r)>>;

  query.a:=x; query.b:=x;

  if x<=mid then query:=pushup(query,query(l,mid,x,y,p<<));

  if y>mid then query:=pushup(query,query(mid+,r,x,y,p<<+));

 end;

 begin

  assign(input,'51nod1766.in'); reset(input);

  assign(output,'51nod1766.out'); rewrite(output);

  readln(n);

  for i:= to n- do

  begin

   readln(x,y,z);

   add(x,y,z);

   add(y,x,z);

  end;

  dfs(,);

  for i:= to time do

  begin

   f[i,]:=a[i]; g[i,]:=b[i];

  end;

  m:=trunc(ln(time)/ln());

  for i:= to m do

   for j:= to time-(<<i)+ do

    if f[j,i-]<f[j+(<<(i-)),i-] then

    begin

     f[j,i]:=f[j,i-]; g[j,i]:=g[j,i-];

    end

     else

     begin

      f[j,i]:=f[j+(<<(i-)),i-];

      g[j,i]:=g[j+(<<(i-)),i-];

     end;

  build(,n,);

  readln(que);

  for i:= to que do

  begin

   readln(x1,y1,x2,y2);

   p:=query(,n,x1,y1,);

   q:=query(,n,x2,y2,);

   ans:=;

   ans:=max(ans,clac(p.a,q.a));

   ans:=max(ans,clac(p.a,q.b));

   ans:=max(ans,clac(p.b,q.a));

   ans:=max(ans,clac(p.b,q.b));

   writeln(ans);

  end;

  close(input);

  close(output);

 end.

巴特西

【51NOD1766】树上的最远点对（线段树，LCA，RMQ）

最新文章

热门文章