题解

首先，读入的时候就将所有的 $w_i$ 减掉 $k$ 。

于是我们要求的就是平均值最接近 0 的。

直接点分治，然后得到一些一端为当前点分中心的路径，设 $a,b$ 为其中两条路径，设 $v_a,v_b$ 为路径的边权和，$t_a,t_b$ 为路径的边数。

二分一个答案，假设差别**小于** $A$。由于题目要求的是下取整，所以我们为了方便，设的是**小于** $A$ ，这样做，最终只需要把答案减一就好了。

那么，如果合并路径 $a,b$ 可以满足条件，那么就会满足：

$$\left|\cfrac{v_a+v_b}{t_a+t_b}\right|<A\\|v_a+v_b|<A(t_a+t_b)\\=\begin{cases}v_a-At_a+v_b-At_b<0\ \ \ \ \ \ (v_a+v_b\geq 0)\\v_a+At_a+v_b+At_b>0\ \ \ \ \ \ (v_a+v_b<0)\end{cases}$$

也就是说，我们只需要对于正的 $v_a$ 和负的 $v_a$ 分开考虑，在保证取到右侧条件的基础上，维护一下最大最小值之类的东西就好了。

具体还是看代码吧。

代码

#include 
     
      #define mp make_pair#define fi first#define se secondusing namespace std;typedef long long LL;LL read(){	LL x=0;	char ch=getchar();	while (!isdigit(ch))		ch=getchar();	while (isdigit(ch))		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();	return x;}const int N=50005;const LL INF=1LL<<60;int n;LL K,ans=INF;vector 
      
       
         > e[N];int vis[N],size[N],Maxsize[N],root,Size;void get_root(int x,int pre){	size[x]=1,Maxsize[x]=0;	for (auto E : e[x])		if (E.fi!=pre&&!vis[E.fi]){			get_root(E.fi,x);			size[x]+=size[E.fi];			Maxsize[x]=max(Maxsize[x],size[E.fi]);		}	Maxsize[x]=max(Maxsize[x],Size-size[x]);	if (Maxsize[x]
        
         =0)		posi[++pc]=Node{cnt,S,ID};	else		nega[++nc]=Node{cnt,S,ID};	for (auto E : e[x])		if (E.fi!=pre&&!vis[E.fi])			dfs(E.fi,x,cnt+1,S+E.se,ID);}pair 
         
           _1,_2;void ckMax(pair 
          
            _3){ if (_3.se>_1.se){ if (_3.fi!=_1.fi) _2=_1; _1=_3; } else if (_3.se>_2.se&&_3.fi!=_1.fi) _2=_3;}void ckMin(pair 
           
             _3){ if (_3.se<_1.se){ if (_3.fi!=_1.fi) _2=_1; _1=_3; } else if (_3.se<_2.se&&_3.fi!=_1.fi) _2=_3;}int check(LL x){ _1=_2=mp(0,INF); for (int i=1,j=nc;i<=pc;i++){ while (j>0&&posi[i].v+nega[j].v>=0) ckMin(mp(nega[j].id,nega[j].v-x*nega[j].t)),j--; if (posi[i].v-x*posi[i].t+(posi[i].id==_1.fi?_2.se:_1.se)<0) return 1; ckMin(mp(posi[i].id,posi[i].v-x*posi[i].t)); } _1=_2=mp(0,-INF); for (int i=pc,j=1;i>=1;i--){ while (j<=nc&&posi[i].v+nega[j].v<0) ckMax(mp(nega[j].id,nega[j].v+x*nega[j].t)),j++; if (posi[i].v+x*posi[i].t+(posi[i].id==_1.fi?_2.se:_1.se)>0) return 1; ckMin(mp(posi[i].id,posi[i].v+x*posi[i].t)); } return 0;}void solve(int x){ Maxsize[0]=n+1; root=pc=nc=0; get_root(x,0); vis[x=root]=1; posi[++pc]=Node{0,0,x}; for (auto E : e[x]) if (!vis[E.fi]) dfs(E.fi,x,1,E.se,E.fi); sort(posi+1,posi+pc+1); sort(nega+1,nega+nc+1); LL L=1,R=ans-1,mid; while (L<=R){ mid=(L+R)>>1; if (check(mid)) R=mid-1; else L=mid+1; } ans=min(ans,L); for (auto E : e[x]) if (!vis[E.fi]) Size=size[E.fi],solve(E.fi);}int main(){ Size=n=read(),K=read(); for (int i=1;i

转载于:https://www.cnblogs.com/zhouzhendong/p/UOJ276.html

你可能感兴趣的文章