题目大意:
给定一颗带边权的树,求一条路径使得这条路径上的边权的平均值最接近一个给定的值。
思路:
既然是求平均值,那么自然而然就想到了分数规划了, 即最小化\(|\frac{\sum_{i=1}^{{len}}w_i}{len}-k|\)。
然后二分答案\(x\),考虑是否存在比\(x\)更优的答案:\(|\frac{\sum_{i=1}^{{len}}w_i}{len}-k|\leq x\),带有绝对值的好像不太好处理,于是将绝对值拆开:\(-x\leq \frac{\sum_{i=1}^{{len}}w_i}{len}-k \leq x\),一般的分数规划都是求一个式子的最值,而这里不难发现需要有两个式子的值同时满足:
\[
\sum_{i=1}^{len}w_i-k+x \geq 0\\
\sum_{i=1}^{len}w_i-k-x \leq 0
\]
由于这里是树上的路径问题,考虑用点分治来解决,考虑以某一个分治重心为根的子树内所有点,按照他们到根的边权和从小到大排序,我们考虑每一个点在满足第一维的情况下最小化第二维的值,这样只需要two point 扫一下就好了。
/*=======================================
* Author : ylsoi
* Time : 2019.2.13
* Problem : uoj276
* E-mail : ylsoi@foxmail.com
* ====================================*/
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<<x<<" "
#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;
using namespace std;
void File(){
freopen("uoj276.in","r",stdin);
freopen("uoj276.out","w",stdout);
}
template<typename T>void read(T &_){
_=0; T f=1; char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0');
_*=f;
}
const int maxn=5e4+10;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
int n;
ll k;
int beg[maxn],to[maxn<<1],las[maxn<<1],cnte=1;
long double w[maxn<<1],c1[maxn<<1],c2[maxn<<1];
void add(int u,int v,long double ww){
las[++cnte]=beg[u],beg[u]=cnte,to[cnte]=v,w[cnte]=ww;
las[++cnte]=beg[v],beg[v]=cnte,to[cnte]=u,w[cnte]=ww;
}
int sz[maxn],min_sz,tot_sz,rt;
bool vis[maxn];
void get_rt(int u,int fh){
int max_sz=0;
sz[u]=1;
for(int i=beg[u];i;i=las[i]){
int v=to[i];
if(v==fh || vis[v])continue;
get_rt(v,u);
max_sz=max(max_sz,sz[v]);
sz[u]+=sz[v];
}
max_sz=max(max_sz,tot_sz-sz[u]);
if(max_sz<min_sz){
min_sz=max_sz;
rt=u;
}
}
struct node{
long double d1,d2;
int from;
bool operator < (const node & tt) const {
return d1<tt.d1;
}
}a[maxn];
int cnt_dis;
void get_dis(int u,int fh,long double d1,long double d2,int from){
a[++cnt_dis]=(node){d1,d2,from};
for(int i=beg[u];i;i=las[i]){
int v=to[i];
if(v==fh || vis[v])continue;
get_dis(v,u,d1+c1[i],d2+c2[i],from);
}
}
void chkmin(int &mn,int &nx,int p){
if(a[p].d2<a[mn].d2){
if(a[p].from!=a[mn].from)nx=mn;
mn=p;
}
else if(a[p].d2<a[nx].d2 && a[p].from!=a[mn].from)nx=p;
}
bool solve(int u){
a[cnt_dis=1]=(node){0,0,u};
for(int i=beg[u];i;i=las[i]){
int v=to[i];
if(vis[v])continue;
get_dis(v,u,c1[i],c2[i],v);
}
sort(a+1,a+cnt_dis+1);
int mn=0,nx=0,p=1,q=1; //[p,q-1] is ok
a[0].d2=INF;
while(a[q].d1<0)++q,++p;
while(q<=cnt_dis){
while(p>1 && a[p-1].d1+a[q].d1>=0)
chkmin(mn,nx,--p);
if(a[mn].from!=a[q].from && a[mn].d2+a[q].d2<=0)return true;
if(a[mn].from==a[q].from && a[nx].d2+a[q].d2<=0)return true;
chkmin(mn,nx,q++);
}
return false;
}
bool divide(int u){
vis[u]=1,get_rt(u,0);
if(solve(u))return true;
for(int i=beg[u];i;i=las[i]){
int v=to[i];
if(vis[v])continue;
tot_sz=sz[v],min_sz=inf;
get_rt(v,0);
if(divide(rt))return true;
}
return false;
}
bool jud(long double x){
REP(i,2,cnte)c1[i]=w[i]+x,c2[i]=w[i]-x;
memset(vis,0,sizeof(vis));
tot_sz=n,min_sz=inf;
get_rt(1,0);
return divide(rt);
}
int main(){
File();
read(n),read(k);
int u,v;
ll ww;
REP(i,1,n-1){
read(u),read(v),read(ww);
add(u,v,(ww-k)*1.0);
}
long double l=0,r=1e13,mid;
while(r-l>1e-3){
mid=(l+r)/2;
if(jud(mid))r=mid;
else l=mid;
//printf("%.10Lf %.10Lf\n",l,r);
}
printf("%lld\n",(ll)(r));
return 0;
}