【来源】

51Nod-1766
vjudge

【题目描述】

n个点被n-1条边连接成了一颗树，给出a_b和cd两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j) |a<=i<=b,c<=j<=d｝
（PS 建议使用读入优化）

【输入格式】

第一行一个数字 n n<=100000。 第二行到第n行每行三个数字描述路的情况，x,y,z (1<=x,y<=n,1<=z<=10000)表示x和y之间有一条长度为z的路。 第n+1行一个数字m，表示询问次数 m<=100000。 接下来m行，每行四个数a,b,c,d。

【输出格式】

共m行，表示每次询问的最远距离

【样例输入】

5 1 2 1 2 3 2 1 4 3 4 5 4 1 2 3 4 5 

【样例输出】

10 

【解析】

线段树+LCA

给你两个区间，问各从一个区间选择一个点，两个点之间的最长路是多少，这里需要注意就是如果第一个区间是a和b最远，第二个区间是c和d最远，那么答案一定是ab，cd，ac，ad，bc，bd，其中一个，于是我们只要用线段树维护合并，外加LCA求两个点的距离即可。

【代码】

#pragma GCC optimize(3,"Ofast","inline") #pragma G++ optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #define RI                 register int #define re(i,a,b)          for(RI i=a; i<=b; i++) #define ms(i,a)            memset(a,i,sizeof(a)) #define MAX(a,b)           (((a)>(b)) ? (a):(b)) #define MIN(a,b)           (((a)<(b)) ? (a):(b)) using namespace std; typedef long long LL; namespace IO { template <typename T> inline void read(T &x){         x=0; char c=0;          T w=0; while (!isdigit(c)) w|=c=='-',c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); if(w) x=-x; } template <typename T> inline void write(T x) { if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else write(x/10),putchar(x%10+'0'); } template <typename T> inline void writesp(T x) { write(x); putchar(' '); } template <typename T> inline void writeln(T x) { write(x); putchar('n'); } } using IO::read; using IO::write; using IO::writesp; using IO::writeln; const int N=1e5+5; const int inf=1e9; struct Edge { int to,nt,w; } e[N<<1]; struct Ans { int len; int a[2]; } t[N<<2]; int n,m,cnt,sum; int h[N],dep[N],f[N][20],tin[N],tout[N]; inline void add(int a,int b,int c) {     e[cnt]=(Edge){b,h[a],c};     h[a]=cnt++; } void dfs(int x,int fa,int d) {     f[x][0]=fa;     tin[x]=++sum;     dep[x]=d; for(int i=h[x]; i!=-1; i=e[i].nt) { int v=e[i].to; if(v==fa) continue; dfs(v,x,d+e[i].w); }     tout[x]=++sum; } inline int ancestor(int x,int y) { return tin[x]<=tin[y] && tout[y]<=tout[x]; } inline int lca(int x,int y) { if(ancestor(x,y)) return x; if(ancestor(y,x)) return y; for(int i=16; i>=0; i--) if(!ancestor(f[x][i],y)) x=f[x][i]; return f[x][0]; } inline int dist(int x,int y) { int k=lca(x,y); return dep[x]+dep[y]-(dep[k]<<1); } #define lch (o<<1) #define rch (o<<1|1) #define mid ((l+r)>>1) void pushup(int o) {     t[o]=t[lch]; if(t[o].len<t[rch].len) t[o]=t[rch]; for(int i=0; i<=1; i++) for(int j=0; j<=1; j++) { int tmp=dist(t[lch].a[i],t[rch].a[j]); if(tmp>t[o].len) {             t[o].len=tmp;             t[o].a[0]=t[lch].a[i];             t[o].a[1]=t[rch].a[j]; } } } void build(int o,int l,int r) { if(l==r) {         t[o].len=0;         t[o].a[0]=l;         t[o].a[1]=r; return; } build(lch,l,mid); build(rch,mid+1,r); pushup(o); }  Ans query(int o,int l,int r,int ll,int rr) { if(l==ll && r==rr) return t[o]; if(rr<=mid) return query(lch,l,mid,ll,rr); else if(ll>mid) return query(rch,mid+1,r,ll,rr); else {                 Ans la=query(lch,l,mid,ll,mid);                 Ans ra=query(rch,mid+1,r,mid+1,rr);                 Ans ta; if(la.len>ra.len) ta=la; else ta=ra; for(int i=0; i<=1; i++) for(int j=0; j<=1; j++) { int tmp=dist(la.a[i],ra.a[j]); if(tmp>ta.len) {                         ta.len=tmp;                         ta.a[0]=la.a[i];                         ta.a[1]=ra.a[j]; } } return ta; } } int main() { read(n); memset(h,-1,sizeof(h)); for(int i=1; i<n; i++) { int x,y,z; read(x); read(y); read(z); add(x,y,z); add(y,x,z); } dfs(1,1,0); for(int j=1; j<=16; j++) for(int i=1; i<=n; i++)         f[i][j]=f[f[i][j-1]][j-1]; build(1,1,n); read(m); while(m--) { int a,b,c,d; read(a); read(b); read(c); read(d);         Ans la,ra; int ans=0;         la=query(1,1,n,a,b);         ra=query(1,1,n,c,d); for(int i=0; i<=1; i++) for(int j=0; j<=1; j++) { int tmp=dist(la.a[i],ra.a[j]);             ans=MAX(ans,tmp); } writeln(ans); } return 0; }