题意: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.
05-14 00:45