分析
首先,设 \(d(i,j)\) 表示当前定义下 i,j 的距离,然后可以发现,当 j 固定,i 在一条路径上移动时,\(d\) 是下凸函数,就是说只会有一个最优解。。
然后考虑 \(f(i)\),表示以 i 为重心时的答案。
有:\(f(i)=\sum_{j\neq i}f(i,j)\)。
然后由于下凸函数相加后也为下凸函数,所以 \(f(i)\) 也为下凸函数。
所以全树只有一个最优位置(不一定为节点),且从此扩散出去的点的答案会变大。
于是考虑链的情况,二分就完事了。
然后放到树上,就可以点分治,每次在根的相邻节点中选出会使答案变小的方向,继续点分。
然后显然我们不能每次都暴力计算 \(f\),我们可以利用导数来快速计算。
注意
codeforces 好像不可以用 long double。。
然后最大值要算好设。。。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
template <class I>
inline void read(I &x){
int f=1;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c&15),c=getchar());
x*=f;
}
int n,w[N];
int head[N],nxt[2*N],ver[2*N],edge[2*N],tot=1;
inline void add(int x,int y,int z){
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
double res=0;
int rt=0,d[N],sz;
bool v[N];
void getsz(int x,int f){
d[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(v[y]||y==f) continue;
getsz(y,x);
d[x]+=d[y];
}
}
void getrt(int x,int f){
d[x]=1;
int mx=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(v[y]||y==f) continue;
getrt(y,x);
d[x]+=d[y];
if(d[y]>mx) mx=d[y];
}
mx=max(mx,sz-d[x]);
if(mx<=sz/2) rt=x;
}
double ds[N];
void calc(int o,int x,int fa,int dis){
res+=(double)pow(dis,1.5)*w[x];
ds[o]+=1.5*pow(dis,0.5)*w[x];
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa) continue;
calc(o,y,x,dis+edge[i]);
}
}
int anss;
double ans=1e20;
void dfs(int x){
getsz(x,0);
sz=d[x];
getrt(x,0);
if(v[x]) return;
v[x=rt]=1;
res=0;
double sds=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
ds[y]=0;
calc(y,y,x,edge[i]);
sds+=ds[y];
}
if(ans>res) ans=res,anss=x;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(sds-2*ds[y]>=0) continue;
dfs(y);
return;
}
}
int main(){
read(n);
for(int i=1;i<=n;i++) read(w[i]);
for(int i=1;i<n;i++){
int x,y,z;
read(x),read(y),read(z);
add(x,y,z);
add(y,x,z);
}
dfs(1);
printf("%d %.7f\n",anss,ans);
return 0;
}