【Codeforces 566 C】Logistical Questions（求导+点分治）

传送门

由于 $x^{\frac 3 2 }$是单调函数
在一条链上可以二分看往哪边更优
求导加起来即可得到变化量

在树上就点分就可以了

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define bg begin
cs int RLEN=(1<<20)+1;
inline char gc(){static char ibuf[RLEN],*ib,*ob;(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;
}
inline int read(){char ch=gc();int res=0;bool f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();return f?res:-res;
}
template<class tp>inline void chemx(tp&a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp&a,tp b){a>b?a=b:0;}
cs int N=200005;
int n,maxn,siz[N],rt,mas;
int w[N],vis[N];
int adj[N],nxt[N<<1],to[N<<1],val[N<<1],cnt;
inline void addedge(int u,int v,int w){nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
void findrt(int u,int fa){siz[u]=1;int son=0;for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(v==fa||vis[v])continue;findrt(v,u),siz[u]+=siz[v];chemx(son,siz[v]);}chemx(son,maxn-siz[u]);if(son<mas)mas=son,rt=u;
}
double f[N],ans;
int ansrt;
void getans(int u,int fa,int dis){ans+=sqrt(dis)*dis*w[u];for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(v==fa)continue;getans(v,u,dis+val[e]);}
}
void calc(int u,int fa,int dis){f[u]=1.5*sqrt(dis)*w[u];for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(v==fa)continue;calc(v,u,dis+val[e]);f[u]+=f[v];}
}
double rans=1e30;
int rrt;
void solve(int u){vis[u]=1;ans=0;getans(u,0,0);if(ans<rans)rans=ans,rrt=u;calc(u,0,0);for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(vis[v])continue;if(f[u]-2*f[v]<=0){maxn=mas=siz[v];findrt(v,0);solve(rt);break;}}
}
int main(){#ifdef Stargazerfreopen("lx.cpp","r",stdin);#endifmas=maxn=n=read();for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<n;i++){int u=read(),v=read(),w=read();addedge(u,v,w),addedge(v,u,w);}findrt(1,0);solve(rt);printf("%d %.8lf",rrt,rans);
}