原题传送门：
51nod 1766 树上最远点对
题意：
n个点被n-1条边连接成了一颗树，给出a~b和c~d两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j) |a<=i<=b,c<=j<=d｝m次询问。
n<=100000，m <= 100000。
题解：
- 求这棵树的dfs序
- 有一个结论：两个子树之间的最长链的两个端点，分别是两个子树中各自的最长链的某个端点。
所以用线段树维护一个子树的最长链的端点u，v，合并两个区间相当于在两个子树四个最长链端点中找两个点使得这两点在所有组合中最长（后面有证明）
- 可以利用ST表求lca的做法快速求的答案（其它做法可能超时）
- 求答案相当于分别在子树中求最长链，最后再合并答案
- 期望复杂度：O(nlogn)
code
{% fold %}
#include <iostream>#include <cstdio>#include <cstring>#define ll long longusing namespace std;ll input(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return f*x;}int n,m;int head[100010],tot=0,top=0,dep[200010],st[400010],pos[200010];int mnp[200010][21],p[200010];int seg[400010][2];ll dis[100010];struct edge{ int to,next; ll val;}e[200010];void makemap(int a,int b,ll d){ e[++tot].to=b; e[tot].val=d; e[tot].next=head[a]; head[a]=tot;}void dfs(int now,int fa){ st[++top]=now; pos[now]=top; for(int i=head[now];i;i=e[i].next){ if(e[i].to!=fa){ dep[e[i].to]=dep[now]+1; dis[e[i].to]=dis[now]+e[i].val; dfs(e[i].to,now); st[++top]=now; } }}void rmq_begin(){ for(int i=i;i<=top;i++){ mnp[i][0]=st[i]; } for(int i=1;i<=20;i++){ for(int j=1;j+(1<<i)-1<=top;j++){ if(dep[mnp[j][i-1]]<dep[mnp[j+(1<<(i-1))][i-1]]) mnp[j][i]=mnp[j][i-1]; else mnp[j][i]=mnp[j+(1<<(i-1))][i-1]; } } p[1]=0; for(int i=2;i<=top;i++){ if(1<<(p[i-1]+1)<i) p[i]=p[i-1]+1; else p[i]=p[i-1]; }}int rmq(int l,int r){ int x=p[r-l+1]; if(dep[mnp[l][x]]<dep[mnp[r-(1<<x)+1][x]]) return mnp[l][x]; else return mnp[r-(1<<x)+1][x];}ll dist(int a,int b){ int g=rmq(min(pos[a],pos[b]),max(pos[a],pos[b])); return dis[a]+dis[b]-2ll*dis[g];}void merge(int a1,int a2,int b1,int b2,int &s1,int &s2){ ll ans=0; if(dist(a1,a2)>ans) ans=dist(a1,a2),s1=a1,s2=a2; if(dist(a1,b1)>ans) ans=dist(a1,b1),s1=a1,s2=b1; if(dist(a1,b2)>ans) ans=dist(a1,b2),s1=a1,s2=b2; if(dist(a2,b1)>ans) ans=dist(a2,b1),s1=a2,s2=b1; if(dist(a2,b2)>ans) ans=dist(a2,b2),s1=a2,s2=b2; if(dist(b1,b2)>ans) ans=dist(b1,b2),s1=b1,s2=b2;}void pushup(int no){ merge(seg[no<<1][0],seg[no<<1][1],seg[no<<1|1][0],seg[no<<1|1][1],seg[no][0],seg[no][1]);}void build(int no,int l,int r){ if(l==r){ seg[no][0]=seg[no][1]=l; return; } int mid=(l+r)>>1; build(no<<1,l,mid); build(no<<1|1,mid+1,r); pushup(no);}void query(int no,int l,int r,int s,int t,int &ans1,int &ans2){ if(l>=s&&r<=t){ merge(ans1,ans2,seg[no][0],seg[no][1],ans1,ans2); return; } int mid=(l+r)>>1; if(s<=mid) query(no<<1,l,mid,s,t,ans1,ans2); if(t>mid) query(no<<1|1,mid+1,r,s,t,ans1,ans2);}int main(){ n=input(); // scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; ll z; x=input(); y=input(); z=input(); // scanf("%d%d%lld",&x,&y,&z); makemap(x,y,z); makemap(y,x,z); } top=0; dep[1]=dis[1]=0; dfs(1,0); rmq_begin(); build(1,1,n); m=input(); for(int i=1;i<=m;i++){ int a,b,c,d; a=input(); b=input(); c=input(); d=input(); // scanf("%d%d%d%d",&a,&b,&c,&d); int a1=a,a2=a,b1=c,b2=c; ll ans=0; query(1,1,n,a,b,a1,a2); query(1,1,n,c,d,b1,b2); // cout<<a1<<" "<<a2<<" "<<b1<<" "<<b2<<endl; ans=max(ans,dist(a1,b1)); // cout<<1<<" "<<ans<<endl; ans=max(ans,dist(a1,b2)); // cout<<2<<" "<<ans<<endl; ans=max(ans,dist(a2,b1)); // cout<<3<<" "<<ans<<endl; ans=max(ans,dist(a2,b2)); // cout<<4<<" "<<ans<<endl; printf("%lld\n",ans); } return 0;}{% endfold %}
补充证明：
结论：两个子树（其实是集合）之间的最长链的两个端点，分别是两个子树（其实是集合）中各自的最长链的某个端点。（子树内两个集合的直径端点构成子树的直径端点）
证明：
两颗子树，连接后变成由一个节点(新的根节点)引出两条边这样的形状，求现在合并后树的最长链。不难想到有两种情况。假如最长链经过两个子树，就像当于在一子树中求离子树的根节点（不一定是在直径上的点）最远的点，另一子树也这么求。然后求得的这两条链与新的根节点的两条边构成了最长链。由树直径的性质只一个点的最远（子树中的）点，仍然是直径的端点。然后还有一种情况，就是链只在一颗子树中，那就是当两棵合并的树规模差距较大时，最长链有可能在规模大的子树中，此时子树的直径就是全树的直径。在问题里我们求的是区间，但两个区间不一定是一棵子树，所以我们是把这个问题搞到虚树上讨论，就解决了不是一课子树的问题了。综上所述：合并两个点集得到的新点集的最长链的端点必定是原先点集直径的端点。（申明：由于本人水平太低，证明不完整）