题意：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保平安
1 type arr=record 2 a,b:longint; 3 end; 4 var f,g:array[1..210000,0..20]of longint; 5 t:array[1..1000000]of arr; 6 a,b,st,dep,dis,head,vet,next,len:array[1..300000]of longint; 7 n,m,i,tot,x,y,z,ans,time,que,j,x1,y1,x2,y2,tmp,tx,ty:longint; 8 p,q:arr; 9 10 procedure add(a,b,c:longint); 11 begin 12 inc(tot); 13 next[tot]:=head[a]; 14 vet[tot]:=b; 15 len[tot]:=c; 16 head[a]:=tot; 17 end; 18 19 function max(x,y:longint):longint; 20 begin 21 if x>y then exit(x); 22 exit(y); 23 end; 24 25 procedure dfs(u,fa:longint); 26 var e,v:longint; 27 begin 28 inc(time); st[u]:=time; a[time]:=dep[u]; b[time]:=u; 29 e:=head[u]; 30 while e<>0 do 31 begin 32 v:=vet[e]; 33 if v<>fa then 34 begin 35 dep[v]:=dep[u]+1; 36 dis[v]:=dis[u]+len[e]; 37 dfs(v,u); 38 inc(time); a[time]:=dep[u]; b[time]:=u; 39 end; 40 e:=next[e]; 41 end; 42 end; 43 44 function min(x,y:longint):longint; 45 begin 46 if x<y then exit(x); 47 exit(y); 48 end; 49 50 function lca(x,y:longint):longint; 51 var len,l,x1,y1:longint; 52 begin 53 x1:=st[x]; y1:=st[y]; 54 if x1>y1 then begin x1:=st[y]; y1:=st[x]; end; 55 len:=y1-x1+1; 56 l:=trunc(ln(len)/ln(2)); 57 if f[x1,l]<f[y1-(1<<l)+1,l] then exit(g[x1,l]) 58 else exit(g[y1-(1<<l)+1,l]); 59 end; 60 61 function clac(x,y:longint):longint; 62 var q:longint; 63 begin 64 q:=lca(x,y); 65 exit(dis[x]+dis[y]-2*dis[q]); 66 end; 67 68 function pushup(x,y:arr):arr; 69 var t:arr; 70 begin 71 t:=x; 72 if clac(y.a,y.b)>clac(t.a,t.b) then t:=y; 73 if clac(x.a,y.a)>clac(t.a,t.b) then 74 begin 75 t.a:=x.a; t.b:=y.a; 76 end; 77 if clac(x.a,y.b)>clac(t.a,t.b) then 78 begin 79 t.a:=x.a; t.b:=y.b; 80 end; 81 if clac(x.b,y.a)>clac(t.a,t.b) then 82 begin 83 t.a:=x.b; t.b:=y.a; 84 end; 85 if clac(x.b,y.b)>clac(t.a,t.b) then 86 begin 87 t.a:=x.b; t.b:=y.b; 88 end; 89 exit(t); 90 end; 91 92 procedure build(l,r,p:longint); 93 var mid:longint; 94 begin 95 if l=r then 96 begin 97 t[p].a:=l; t[p].b:=l; 98 exit; 99 end; 100 mid:=(l+r)>>1; 101 build(l,mid,p<<1); 102 build(mid+1,r,p<<1+1); 103 t[p]:=pushup(t[p<<1],t[p<<1+1]); 104 end; 105 106 function query(l,r,x,y,p:longint):arr; 107 var mid:longint; 108 begin 109 if (l>=x)and(r<=y) then exit(t[p]); 110 mid:=(l+r)>>1; 111 query.a:=x; query.b:=x; 112 if x<=mid then query:=pushup(query,query(l,mid,x,y,p<<1)); 113 if y>mid then query:=pushup(query,query(mid+1,r,x,y,p<<1+1)); 114 end; 115 116 begin 117 assign(input,'51nod1766.in'); reset(input); 118 assign(output,'51nod1766.out'); rewrite(output); 119 readln(n); 120 for i:=1 to n-1 do 121 begin 122 readln(x,y,z); 123 add(x,y,z); 124 add(y,x,z); 125 end; 126 dfs(1,0); 127 for i:=1 to time do 128 begin 129 f[i,0]:=a[i]; g[i,0]:=b[i]; 130 end; 131 m:=trunc(ln(time)/ln(2)); 132 for i:=1 to m do 133 for j:=1 to time-(1<<i)+1 do 134 if f[j,i-1]<f[j+(1<<(i-1)),i-1] then 135 begin 136 f[j,i]:=f[j,i-1]; g[j,i]:=g[j,i-1]; 137 end 138 else 139 begin 140 f[j,i]:=f[j+(1<<(i-1)),i-1]; 141 g[j,i]:=g[j+(1<<(i-1)),i-1]; 142 end; 143 build(1,n,1); 144 readln(que); 145 for i:=1 to que do 146 begin 147 readln(x1,y1,x2,y2); 148 p:=query(1,n,x1,y1,1); 149 q:=query(1,n,x2,y2,1); 150 ans:=0; 151 ans:=max(ans,clac(p.a,q.a)); 152 ans:=max(ans,clac(p.a,q.b)); 153 ans:=max(ans,clac(p.b,q.a)); 154 ans:=max(ans,clac(p.b,q.b)); 155 writeln(ans); 156 end; 157 close(input); 158 close(output); 159 end.