现在有n个数，范围是1——n。初始时每个数都在不同集合里。 有n-1个操作，每次操作给定x,y，把x和y所在集合合并（保证x,y不在同一个集合），然后输出新集合最小、最大值在给定的规则下最快能在什么时候相遇。 有T组数据。 n≤100000 T≤5
首先是对于一个集合求答案的问题。 如果确定了在哪两个数中间相遇，那么答案就是两个数与对应位置距离的较大值。 枚举一定会超时，但是有一个想法：首先确定一个中间位置mid=(min+max)/2。 然后找到集合里小于等于mid的最大值，和大于mid的最小值，然后走到这里。 但是这样有反例，如：1,2,10,11,17。mid=9，如果走到2与10中间，花费为11，然而走到10与11中间花费为9.5 如果两个不跨过mid的方案都在mid的同一边，显然靠近mid的答案更优。那么现在已经知道了mid左边、右边的第一个数，可以把两个位置左移一位或右移一位，就有三种情况，答案必然在这中间产生。
现在问题就是，如何维护集合。
首先集合的合并可以用并查集完成，然后用线段树查询每个值，合并区间时，由于并查集是连成一棵树的，那么就把维护的集合合并到根，用线段树合并解决。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=50005,maxm=1600005; typedef long long LL; typedef double db; int T,n,f[maxn],tot,root[maxn]; char c; struct segment_tree { int l,r,Min,Max; }t[maxm]; int read() { for (c=getchar();c<'0' || c>'9';c=getchar()); int x=c-48; for (c=getchar();c>='0' && c<='9';c=getchar()) x=x*10+c-48; return x; } void init(int l,int r,int g,int &x) { x=++tot; t[x].l=t[x].r=0; t[x].Min=t[x].Max=g; if (l==r) return; int mid=l+r>>1; if (g<=mid) init(l,mid,g,t[x].l);else init(mid+1,r,g,t[x].r); } int get(int x) { return (!f[x])?x:f[x]=get(f[x]); } int Union(int l,int r,int x,int y) { if (!x && !y) return 0; if (!x) return y; if (!y) return x; int mid=l+r>>1; t[x].l=Union(l,mid,t[x].l,t[y].l); t[x].r=Union(mid+1,r,t[x].r,t[y].r); if (t[y].Min<t[x].Min) t[x].Min=t[y].Min; if (t[y].Max>t[x].Max) t[x].Max=t[y].Max; return x; } int getmax(int l,int r,int g,int x) { if (!x) return 0; if (l==r) return l; int mid=l+r>>1; if (g<=mid) return getmax(l,mid,g,t[x].l); int tmp=getmax(mid+1,r,g,t[x].r); if (tmp) return tmp; return t[t[x].l].Max; } int getmin(int l,int r,int g,int x) { if (!x) return 0; if (l==r) return l; int mid=l+r>>1; if (g>mid) return getmin(mid+1,r,g,t[x].r); int tmp=getmin(l,mid,g,t[x].l); if (tmp) return tmp; return t[t[x].r].Min; } void work() { tot=0; n=read(); for (int i=1;i<=n;i++) { f[i]=0; init(1,n,i,root[i]); } for (int i=1;i<n;i++) { int x=get(read()),y=get(read()); f[y]=x; Union(1,n,root[x],root[y]); int p=t[root[x]].Min,q=t[root[x]].Max; db mid=(db)(p+q)/2,ans; db a1,a2=getmax(1,n,mid,root[x]),a3=getmin(1,n,a2+1,root[x]),a4; ans=max(q-a3,a2-p)+(a3-a2)/2; if (a2>1)a1=getmax(1,n,a2-1,root[x]);else a1=0; if (a1>0) ans=min(ans,max(q-a2,a1-p)+(a2-a1)/2); if (a3<n)a4=getmin(1,n,a3+1,root[x]);else a4=0; if (a4>0) ans=min(ans,max(q-a4,a3-p)+(a4-a3)/2); printf("%.1lf\n",ans); } } int main() { for (T=read();T--;work()); return 0; }