[WC2010]重建方案：分数规划、点分治与单调队列的应用分析

#include
#include
#include
#include
#define N 100002
#define inf 2e9
#define Re register
using namespace std;
typedef long long ll;
const double eps=1e-4;
double mid,ans,ma,deep[N],man[N];
int tot,head[N],dp[N],q[N],minl,maxl,size[N],maxdeep,root,sum,n,dep[N],que[N],L,R;
bool vis[N],visit[N];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
struct edge{int n,to,l;}e[N<<1];
inline void add(int u,int v,int l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}
void getsize(int u,int fa){
size[u]=1;
for(Re int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
int v=e[i].to;
getsize(v,u);size[u]+=size[v];
}
}
inline int mx(int a,int b){return a>b?a:b;}
inline double maxx(double a,double b){return a>b?a:b;}
void getroot(int u,int fa){
dp[u]=0;size[u]=1;
for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]&&e[i].to!=fa){
int v=e[i].to;
getroot(v,u);size[u]+=size[v];
dp[u]=mx(dp[u],size[v]);
}
dp[u]=mx(dp[u],sum-size[u]);
if(dp[u]u;
}
void getdeep(int u,int fa){
maxdeep=mx(maxdeep,dep[u]);
for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]&&e[i].to!=fa){
int v=e[i].to;deep[v]=deep[u]+e[i].l-mid;dep[v]=dep[u]+1;
getdeep(v,u);
}
}
void getcalc(int u,int fa){
man[dep[u]]=maxx(man[dep[u]],deep[u]);
for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]&&e[i].to!=fa){
int v=e[i].to;getcalc(v,u);
}
}
inline bool getcheck(int u){
maxdeep=0;bool tag=0;
for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;deep[v]=e[i].l-mid;dep[v]=1;
getdeep(v,u);
int h=1,t=1;que[h]=v;visit[v]=1;
while(h<=t){
int x=que[h++];
for(int j=head[x];j;j=e[j].n){
int v=e[j].to;
if(!vis[v]&&!visit[v]&&v!=u)que[++t]=v,visit[v]=1;
}
}
int p=0;L=1;R=0;q[++R]=0;
for(Re int i=t;i>=1;--i){
int x=que[i];visit[x]=0;
while(p+dep[x]maxdeep){
int x=++p;
while(L<=R&&man[x]>=man[q[R]])R--;
q[++R]=x;
}
while(L<=R&&q[L]+dep[x];
if(L<=R&&deep[x]+man[q[L]]>=0)tag=1;
}
getcalc(v,u);
}
for(Re int i=1;i<=maxdeep;++i)man[i]=-inf;
return tag;
}
inline void getans(int u){
double l=ans,r=ma;
while(r-l>eps){
mid=(l+r)/2.0;
if(getcheck(u)){ans=mid;l=mid;}else r=mid;
}
}
void solve(int u){
getans(u);vis[u]=1;
for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;
root=n+1;sum=size[v];
getroot(v,u);//getsize(root,0);
solve(root);
}
}
int main(){
n=rd();minl=rd();maxl=rd();int u,v,w;
for(int i=1;i<=n;++i)man[i]=-inf;
ma=-1e9;ans=1e9;
for(Re int i=1;ii){
u=rd();v=rd();w=rd();ma=maxx(ma,(double)w);ans=min(ans,(double)w);
add(u,v,w);add(v,u,w);
}
dp[root=n+1]=n;sum=n;
getroot(1,0);//getsize(root,0);
solve(root);
printf("%.3lf",ans);
return 0;
}