连一条长度为len的边，使得基环树的直径最小
结论：一定连在某条直径两个点上（否则更靠近不劣）
然后二分答案判定。
dp[i]：链上一个点往下延伸的最大深度
考虑对于任意两个点对最短路径都不能大于mid
就是：任意的(i<j)，min(sum[j]-sum[i]+dp[i]+dp[j],len+|sumb-sumj|+|sumi-suma|+dp[i]+dp[j])<mid
前面的min比较好处理，直接按照sum+dp,dp-sum排序，双指针搞一下
不能满足前面的min的点对i，j，必然要满足后面的。
把绝对值拆开成4个，对于任意的i，j，选择的a，b都要使得这些4*k个不等式成立。
suma,sumb移项，所以4个不等式右边都要取最大的（任意转化为最值）
所以双指针的时候可以再用树状数组（为了i<j）找到4个lim
然后移项。
枚举b，sum升序降序排序，四指针维护。
每次看区间的交是否为空。
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=1e5+5; const ll inf=0x3f3f3f3f3f3f3f3f; int n; struct node{ int nxt,to; int val; }e[2*N]; int hd[N],cnt; void add(int x,int y,int z){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].val=z; hd[x]=cnt; } ll ans,len; ll L,R; int mem[N],fa[N],vf[N]; int on[N]; ll sum[N]; struct po{ ll v; int id; po(){} po(ll vv,int dd){ v=vv;id=dd; } }; struct qs{ po p[N]; int sz; void push(ll v,int d){ p[++sz]=po(v,d); } void clear(){ sz=0; } il po &operator[](const int &x){return p[x];} il const po &operator[](const int &x) const {return p[x];} }su,sd,up,dw;//member's number is num bool cmpu(po a,po b){//sheng return a.v<b.v; } bool cmpd(po a,po b){//jiang return a.v>b.v; } int st,nd,num; ll mx; struct tr{ ll f[N]; void clear(){ memset(f,-0x3f,sizeof f); } void ins(int x,ll v){ for(;x<=n;x+=x&(-x)) f[x]=max(f[x],v); } ll query(int x){ ll ret=-inf; for(;x;x-=x&(-x)) ret=max(ret,f[x]); return ret; } }t[2]; //t[0]:dp-sum //t[1]:dp+sum void dfs1(int x,ll dis){ if(dis>mx) { mx=dis;st=x; } for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]) continue; fa[y]=x; dfs1(y,dis+e[i].val); } } void dfs2(int x,ll dis){ if(dis>mx){ mx=dis;nd=x; } for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]) continue; fa[y]=x; vf[y]=e[i].val; dfs2(y,dis+e[i].val); } } ll dp[N]; void fin(int x){ dp[x]=0; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]||on[y]) continue; fa[y]=x; fin(y); L=max(L,dp[x]+dp[y]+e[i].val); dp[x]=max(dp[x],dp[y]+e[i].val); } } struct pointer{ int ptr; ll lim; void clear(){ ptr=0;lim=-inf; } void upda(ll v){ lim=max(lim,v); } }p[5]; pair<int,int>tp; void con(int l,int r){ tp.fi=max(tp.fi,l); tp.se=min(tp.se,r); } bool che(ll mid){ ///warning!!!! dp[mem[...[].id]] t[0].clear();t[1].clear(); for(reg i=1;i<=4;++i) p[i].clear(); int ptr=0; for(reg j=1;j<=num;++j){ while(ptr<num&&dw[ptr+1].v+up[j].v>mid) { ++ptr; t[0].ins(dw[ptr].id,dw[ptr].v); t[1].ins(dw[ptr].id,sum[dw[ptr].id]+dp[mem[dw[ptr].id]]); } if(ptr){ ll djss=dp[mem[up[j].id]]-sum[up[j].id],djas=up[j].v; ll diss=t[0].query(up[j].id-1),dias=t[1].query(up[j].id-1); p[1].upda(len-mid+djss+dias); p[2].upda(len-mid+diss+djas); p[3].upda(len-mid+dias+djas); p[4].upda(len-mid+diss+djss); } } p[1].ptr=p[4].ptr=1; for(reg b=1;b<=num;++b){ while(p[1].ptr<=num&&su[p[1].ptr].v-p[1].lim<su[b].v) ++p[1].ptr; while(p[2].ptr<num&&su[p[2].ptr+1].v+p[2].lim<=su[b].v) ++p[2].ptr; while(p[3].ptr<num&&-sd[p[3].ptr+1].v+p[3].lim<=su[b].v) ++p[3].ptr; while(p[4].ptr<=num&&-sd[p[4].ptr].v-p[4].lim<su[b].v) ++p[4].ptr; tp.fi=1;tp.se=num; con(p[1].ptr,num); con(1,p[2].ptr); con(num-p[3].ptr+1,num); con(1,num-p[4].ptr+1); if(tp.fi<=tp.se) return true; } return false; ///warning!!!! dp[mem[...[].id]] } void clear(){ ans=inf;num=0;st=nd=0; memset(sum,0,sizeof sum); memset(fa,0,sizeof fa); memset(vf,0,sizeof vf); memset(on,0,sizeof on); memset(hd,0,sizeof hd); su.clear();sd.clear();up.clear();dw.clear(); cnt=0; L=0,R=0; } int main(){ while(1){ clear(); rd(n);rd(len); if(n==0&&len==0) break; mx=-1; int x,y,z; for(reg i=1;i<n;++i){ rd(x);rd(y);rd(z); add(x,y,z);add(y,x,z); } if(n==1){ puts("0");continue; } dfs1(1,0); fa[st]=0; mx=-1; dfs2(st,0); /*RRR*/ R=mx; num=0; x=nd; while(x){ mem[++num]=x; on[x]=1; sum[num]=sum[num-1]+vf[mem[num-1]]; x=fa[x]; } memset(fa,0,sizeof fa); /*LLL*/ for(reg i=1;i<=num;++i){ fin(mem[i]); } for(reg i=1;i<=num;++i){ su.push(sum[i],i); sd.push(sum[i],i); up.push(dp[mem[i]]+sum[i],i); dw.push(dp[mem[i]]-sum[i],i); } sort(su.p+1,su.p+num+1,cmpu); sort(sd.p+1,sd.p+num+1,cmpd); sort(up.p+1,up.p+num+1,cmpu); sort(dw.p+1,dw.p+num+1,cmpd); while(L<=R){ ll mid=(L+R)/2; if(che(mid)){ ans=mid;R=mid-1; }else L=mid+1; } printf("%lld ",ans); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
二分判定突破口
判定min的或关系。不涉及a,b的先去掉，对于剩下的任意变成最值，纯粹解不等式了。
大量运用排序+双指针。