[清华集训2016]汽水

[清华集训2016]汽水

UOJ
BZOJ
这是一个常数大的人过不了的算法
分数规划套点分治,暴力离散化然后树状数组查询
复杂度:(O(nlog^3n))
所以有大佬教我卡卡常嘛??

#define lb(i) (i&-i)
#define ll long long
#include<bits/stdc++.h>
using namespace std;
const int _=5e4+5;
const ll inf=1e18;
inline ll re(){
    ll x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,num,cnt,tot,rt,Rt,ok;
int h[_],ms[_],sz[_],vis[_];
ll k,l,r=inf,mid,ans;
ll val[_],o[_<<1],f[_],g[_],t[_<<1];
vector<int>son[_];
struct edge{int to,next;ll w;}e[_<<1];
inline void link(int u,int v,ll w){
	e[++cnt]=(edge){v,h[u],w},h[u]=cnt;
	e[++cnt]=(edge){u,h[v],w},h[v]=cnt;
}
inline void add(int i,ll v){while(i<=num)t[i]=max(t[i],v),i+=lb(i);}
inline void mdf(int i,ll v){while(i<=num)t[i]=v,i+=lb(i);}
inline ll qmax(int i){ll res=-inf;while(i)res=max(res,t[i]),i-=lb(i);return res;}
void qrt(int u,int fa){
	sz[u]=1,ms[u]=0;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==fa||vis[v])continue;
		qrt(v,u),sz[u]+=sz[v],
		ms[u]=max(ms[u],sz[v]);
	}
	ms[u]=max(ms[u],tot-sz[u]);
	if(ms[u]<ms[rt])rt=u;
}
void bu(int u){
	vis[u]=1;int now=tot;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(vis[v])continue;
		if(sz[u]<sz[v])tot=now-sz[u];
		else tot=sz[v];rt=0,qrt(v,0);
		son[u].push_back(rt);bu(rt);
	}
}
void dfs(int u,int fa,int dep,ll dis){
	val[u]=dis+dep*mid;
	f[u]=o[++num]=dis-dep*mid;
	g[u]=o[++num]=-f[u];
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==fa||vis[v])continue;
		dfs(v,u,dep+1,dis+e[i].w);
	}
}
void calc(int u,int fa){
	g[u]=lower_bound(o+1,o+num+1,g[u])-o;
	if(qmax(g[u]-1)+val[u]>0)ok=1;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v^fa&&!vis[v])calc(v,u);
	}
}
void pre(int u,int fa){
	f[u]=lower_bound(o+1,o+num+1,f[u])-o;
	add(f[u],val[u]);
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v^fa&&!vis[v])pre(v,u);
	}
}
void clear(int u,int fa){
	mdf(f[u],-inf);
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v^fa&&!vis[v])clear(v,u);
	}
}
void solve(int u){
	vis[u]=1;num=0;
	dfs(u,0,0,0);
	sort(o+1,o+num+1);
	num=unique(o+1,o+num+1)-o-1;
	f[u]=lower_bound(o+1,o+num+1,0)-o;
	add(f[u],0);
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;if(vis[v])continue;
		calc(v,u);if(ok)return;pre(v,u);
	}
	mdf(f[u],-inf);
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(!vis[v])clear(v,u);
	}
	for(int i=h[u],j=0;i;i=e[i].next){
		int v=e[i].to;if(ok)return;
		if(!vis[v])solve(son[u][j++]);
	}
}
int main(){
    tot=ms[0]=n=re();k=re();
	for(int i=1;i<n;++i){
		int u=re(),v=re();ll w=re()-k;
		link(u,v,w);r=min(r,abs(w))+1;
	}
	qrt(1,0);bu(Rt=rt);
	while(l<=r){
		mid=(l+r)>>1;
		memset(vis,0,sizeof(vis));
		memset(t,-0x7f,sizeof(t));
		ok=0;solve(Rt);
		if(ok)ans=r=mid-1;
		else l=mid+1;
	}
	printf("%lld
",ans);
	return 0;
}