题目
题目描述
牛牛来到了一个盛产汽水的国度旅行。
这个国度的地图上有 $n$ 个城市，这些城市之间用 $n−1$ 条道路连接，任意两个城市之间，都存在一条路径连接。这些城市生产的汽水有许多不同的风味，在经过道路 $i$ 时，牛牛会喝掉 $w_i$ 的汽水。牛牛非常喜欢喝汽水，但过量地饮用汽水是有害健康的，因此，他希望在他旅行的这段时间内，平均每天喝到的汽水的量尽可能地接近给定的一个正整数 $k$ 。
同时，牛牛希望他的旅行计划尽可能地有趣，牛牛会先选择一个城市作为起点，然后每天通过一条道路，前往一个没有去过的城市，最终选择在某一个城市结束旅行。
牛牛还要忙着去喝可乐，他希望你帮他设计出一个旅行计划，满足每天$\vert 平均每天喝到的汽水−k\vert$ 的值尽量小，请你告诉他这个最小值。
输入格式
第一行两个正整数 $n,k$ 。
接下来 $n−1$ 行，每行三个正整数 $u_i,v_i,w_i$，表示城市 $u_i$ 和城市 $v_i$ 之间有一条长度为 $w_i$ 的道路连接。
同一行相邻的两个整数均用一个空格隔开。
输出格式
一行一个整数，表示 $\vert 平均每天喝到的汽水−k\vert$ 的最小值的整数部分，即你只要将这个最小值向下取整然后输出即可。
样例一
input
5 21
1 2 9
1 3 27
1 4 3
1 5 12
output
1
explanation
在图中，路径5->1->3是一条最合适的路线，总计喝到的汽水的量是 $27+12=39$, 平均每天喝到的汽水量是 $39÷2=19.5$, $\vert 19.5−21\vert =1.5$，向下取整后得到 $1$，因此答案是 $1$。
样例二
见样例数据下载
限制与约定
对于 $20\%$ 的数据，$n≤1000$。
对于另外 $20\%$ 的数据，保证编号为 $i(1≤i≤n−1)$ 的节点和编号为 $i+1$ 的节点之间连接了一条边。
对于另外 $20\%$ 的数据，保证数据是以$1$为根的完全二叉树（在完全二叉树中，节点 $i(2≤i≤n)$ 和节点 $⌊i÷2⌋$ 之间有一条道路）。
对于另外 $20\%$ 的数据，保证除节点 $1$ 以外，其他节点和节点 $1$ 之间都有一条道路。
对于 $100\%$ 的数据，$1≤n≤5×10^4,0≤w_i≤10^{13},0≤k≤10^{13}$。
时间限制：$5s$
空间限制：$512MB$
题解
每条边权都可以先$-k$，然后这题一脸可以二分的样子
因为向下取整，所以可以直接二分整数
假设二分答案为$mid$，设$W_t$为路径$t$边权和，路径$L$合法必须满足条件$\left\vert \frac{W_L}{\vert L\vert}\right\vert<mid$
拆开绝对值有$-mid<\frac{W_L}{\vert L\vert}<mid$
统计树上路径存在性问题常用点分治，现在考虑对于$x$，有两条$x$不同子树的路径$S_l,S_r$，条件就变成了$-mid<\frac{W_{S_l}+W_{S_r}}{\vert S_l\vert+\vert S_r\vert}<mid$
设$A=W_{S_l},A’=W_{S_r},B=\vert S_l\vert,B’=\vert S_r\vert$，$B+B’$的值肯定为正，所以可以分$A+A’$的正负讨论
-
如果$A+A’\ge 0$，$>-mid$的条件可以直接省去，则有$A+A’<mid(B+B’)$，即$A-midB<midB’-A’$
-
如果$A+A’<0$，$<mid$的条件可以直接省去，则有$A+A’>-mid(B+B’)$，即$A+midB>-midB’-A’$
发现如果按$A$排序，可以双指针$O(n)$求解，维护最值和另一个子树里的最值即可
调了半天发现点分治写错了emmmm
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5e4+5;
struct p{
int x,y;
LL d;
}c[MAX<<1];
struct q{
int x,y;
}C[MAX];
struct o{
int x,l;
LL d;
bool operator< (const o &a)
const{
return d<a.d;
}
}d[MAX];
vector<int> vec[MAX];
int n,num,rt,Rt,Sum,tot;
LL K,mx=1e18;
int h[MAX],f[MAX],siz[MAX];
bool use[MAX];
LL read()
{
LL x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y,LL d)
{
mx=min(mx,abs(d-K));
c[++num]=(p){h[x],y,d-K},h[x]=num;
c[++num]=(p){h[y],x,d-K},h[y]=num;
}
void GET_ROOT(int x=1,int fa=0)
{
siz[x]=1,f[x]=0;
for(int i=h[x];i;i=c[i].x)
if((!use[c[i].y])&&(c[i].y^fa)) GET_ROOT(c[i].y,x),siz[x]+=siz[c[i].y],f[x]=max(f[x],siz[c[i].y]);
f[x]=max(f[x],Sum-siz[x]);
if(f[x]<f[rt]) rt=x;
}
void GET_NUM(int x,int fa,LL D,int s,int l=1)
{
d[++tot]=(o){s,l,D};
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y]&&(c[i].y^fa)) GET_NUM(c[i].y,x,D+c[i].d,s,l+1);
}
LL Ax(o a,LL mid) {return mid*a.l-a.d;}
LL Bx(o a,LL mid) {return a.d-mid*a.l;}
LL Cx(o a,LL mid) {return -mid*a.l-a.d;}
LL Dx(o a,LL mid) {return a.d+mid*a.l;}
void Dfs(int x=Rt)
{
use[x]=1;
int xsum=Sum;
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y])
{
if(siz[c[i].y]>siz[x]) Sum=xsum-siz[x];
else Sum=siz[c[i].y];
f[rt=0]=Sum,GET_ROOT(c[i].y,x),vec[x].push_back(rt),Dfs(rt);
}
}
bool dfs(LL mid,int x=Rt)
{
use[x]=1,d[tot=1]=(o){-1,0,0};
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y]) GET_NUM(c[i].y,x,c[i].d,c[i].y);
sort(d+1,d+1+tot);
o A=(o){0,0,-1e18},B=A;
for(int i=1,L=tot;i<=tot;++i)
{
while(L&&d[L].d+d[i].d>=0)
{
if(A.d<Ax(d[L],mid))
{
if(d[L].x!=A.x) B=A,A.x=d[L].x;
A.d=Ax(d[L],mid);
}
else if(B.d<Ax(d[L],mid)&&d[L].x!=A.x) B.x=d[L].x,B.d=Ax(d[L],mid);
--L;
}
if(A.x==d[i].x) if(Bx(d[i],mid)<B.d) return 1;
if(A.x!=d[i].x) if(Bx(d[i],mid)<A.d) return 1;
}
A=(o){0,0,1e18},B=A;
for(int i=tot,L=1;i>=1;--i)
{
while(L<=tot&&d[L].d+d[i].d<0)
{
if(A.d>Cx(d[L],mid))
{
if(d[L].x!=A.x) B=A,A.x=d[L].x;
A.d=Cx(d[L],mid);
}
else if(B.d>Cx(d[L],mid)&&d[L].x!=A.x) B.x=d[L].x,B.d=Cx(d[L],mid);
++L;
}
if(A.x==d[i].x) if(Dx(d[i],mid)>B.d) return 1;
if(A.x!=d[i].x) if(Dx(d[i],mid)>A.d) return 1;
}
for(int i=0,CNT=vec[x].size();i<CNT;++i)
if(dfs(mid,vec[x][i])) return 1;
return 0;
}
int main()
{
n=read(),K=read();
for(int i=1,x,y;i<n;++i)
x=read(),y=read(),add(x,y,read());
Sum=f[rt]=n,GET_ROOT(),Rt=rt;
LL l=1,r=mx,ans=mx+1;
Dfs();
while(l<=r)
{
LL mid(l+r>>1);
memset(use,0,sizeof(use));
if(dfs(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
return printf("%lld",ans-1),0;
}
