这个中位数显然可以通过二分来确定。检验的方法就是把边权大于等于检验值的设为1，小于的设为-1，看是否有一条路径边权和大于等于0。
关于长度的限制则可以用点分治。对于节点u，先把它的子节点按子树从小到大排序，保证复杂度，开个桶记录一下长度为d的边最大的权值bkt[d].w，以及其端点bkt[d].x，然后逐一合并。到子树v时，先dfs一下，求出子树内的不同长度下最大权值，用t1数组记录一下，然后对于t1内每个值，需要寻找一个滑动区间内的最大值，类似于单调队列的思路。若没有找到可行解则把t1合并到bkt中，再做下一个子树。
貌似把二分套在点分治里面常数会比较小。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; struct edge1{ int u,v,w; }d1[N]; struct edge{ int y,next,w; }data[N<<1]; struct node{ int w,x; }t1[N],bkt[N]; bool vis[N]; int n,l,r,a,b,root,s,cnt,ans,ansu,ansv,tmpu,tmpv,num,mx1,mx2; int h[N],siz[N],son[N],que[N],tree[N]; inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } inline bool cmp1(edge1 i,edge1 j){return i.w<j.w;} inline bool cmp3(int i,int j){return siz[data[i].y]<siz[data[j].y];} inline void addedge(int u,int v,int w){ data[++num].y=v,data[num].w=w,data[num].next=h[u],h[u]=num; data[++num].y=u,data[num].w=w,data[num].next=h[v],h[v]=num; } void getroot(int u,int fa){ siz[u]=1,son[u]=0; for(int i=h[u],v;i!=-1;i=data[i].next){ v=data[i].y; if(!vis[v]&&v!=fa){ getroot(v,u); siz[u]+=siz[v];if(son[u]<siz[v])son[u]=siz[v]; } } if(s-siz[u]>son[u])son[u]=n-siz[u]; if(son[u]<son[root])root=u; } inline int max1(int a,int b){return a>b?a:b;} void getdis(int u,int fa,int d,int w,int x){ if(d>mx2)mx2=d; for(int i=h[u],v;i!=-1;i=data[i].next){ v=data[i].y; if(!vis[v]&&fa!=v){ int uw=w+(data[i].w>=x?1:-1),ud=d+1; if(t1[ud].w<uw)t1[ud].w=uw,t1[ud].x=v; getdis(v,u,ud,uw,x); } } } inline bool check(int u,int x){ bkt[0].w=0,bkt[0].x=u;mx1=0,mx2=1; for(int i=1,v;i<=cnt;++i){ v=data[tree[i]].y; for(int j=2;j<=siz[v];++j)t1[j].w=-1e9; int tmp=data[tree[i]].w>=x?1:-1; t1[1].w=tmp,t1[1].x=v; getdis(v,u,1,t1[1].w,x); int a1=1,b1=0,a2=mx1,b2=mx1; for(int j=1;j<=mx2;++j){ while(a2>=0&&j+a2>=l){ while(a1<=b1&&bkt[que[b1]].w<=bkt[a2].w)--b1; que[++b1]=a2; --a2; } while(b2>=-1&&j+b2>=r){ while(a1<=b1&&que[a1]>b2)++a1; --b2; } if(a1<=b1&&t1[j].w+bkt[que[a1]].w>=0){ tmpu=t1[j].x,tmpv=bkt[que[a1]].x;return true; } } while(mx1<mx2)bkt[++mx1].w=-1e9; for(int j=1;j<=mx1;++j) if(bkt[j].w<t1[j].w)bkt[j].x=t1[j].x,bkt[j].w=t1[j].w; } return false; } void divide(int u){ vis[u]=true; int aa=a,bb=b;cnt=0; for(int i=h[u],v;i!=-1;i=data[i].next){ v=data[i].y; if(!vis[v]){ siz[v]=siz[v]>siz[u]?s-siz[u]:siz[v]; tree[++cnt]=i; } } sort(tree+1,tree+cnt+1,cmp3); while(aa<=bb){ int mid=(aa+bb)>>1; if(check(u,mid))aa=mid+1; else bb=mid-1; if(bb<=ans)break; } if(bb>ans)ans=bb,ansu=tmpu,ansv=tmpv; for(int i=h[u],v;i!=-1;i=data[i].next){ v=data[i].y; if(!vis[v]&&siz[v]>l){ s=siz[v],root=0;getroot(v,u);divide(root); } } } int main(){ n=read(),l=read(),r=read(); num=-1;memset(h,-1,sizeof h); a=1e9,b=0; for(int i=1;i<n;++i)d1[i].u=read(),d1[i].v=read(),d1[i].w=read(); sort(d1+1,d1+n,cmp1);d1[0].w=-1; for(int i=1,qwq=0;i<n;++i){ if(d1[i].w!=d1[i-1].w)++qwq; addedge(d1[i].u,d1[i].v,qwq); if(qwq<a)a=qwq;if(qwq>b)b=qwq; } memset(vis,false,sizeof vis);root=0,son[0]=n,s=n,ans=-1; getroot(1,0);divide(root); printf("%d %d",ansu,ansv); return 0; }
