题解 CF566C【Logistical Questions】

· · 题解

CF566C Logistical Questions解题报告：

更好的阅读体验

题意

给定一颗 n 个点，带点权和边权的树，设一条路径的权值为边权的 1.5 次方，求树的带权重心。

分析

大清新题。

我们发现真正的带权重心不一定在结点上（虽然答案在结点上），可能在一条边的某个位置，设其为 G。如果重心恰好在一个结点上，我们钦定它在这个点相连的一条边无限接近端点的一个位置。

先考虑树只有两个点的情况，设唯一的一条边为 (x,y,z)，那么如果当前在边上与 x 的距离为 p 的位置，那么权值和为：

f(p)=v_xp^{1.5}+v_y(z-p)^{1.5}

我们对其求导，得到 f'(p)=1.5(v_x\sqrt p-v_y\sqrt{z-p})。

带入边的两个端点 0 和 z 得到 f'(0)=-1.5v_y\sqrt{z}，f'(z)=1.5v_x\sqrt{z}。

于是我们发现点在边上移动时，靠近带权重心时权值和减小，远离带权重心是权值和增加，也就是这个函数是严格下凸的。

我们将情况扩展到树上，在一条边上运动时，新的距离和 g(p) 可以看做若干个 f 的和，于是它仍然是严格下凸的。

这是一个非常好的性质，它告诉我们如果一个点靠近重心，权值和一定减小，否则一定增加。

我们从任意一个点开始，每次通过它子树中所有点来计算每一条边的导数，取负数的那一条边。这样做的复杂度是 O(n^2) 的。

但是我们发现可以在点分治中做这样的操作，具体就每次走一条边后就直接跳到这个子树重心，这样复杂度就是 O(n\log n) 了。

代码

#include<stdio.h>
#include<math.h>
#define inf 1000000000
const int maxn=200005,maxm=maxn<<1;
int n,e,stp,minn,pos,ans;
int v[maxn],start[maxn],to[maxm],then[maxm],worth[maxm],vis[maxn],size[maxn],fin[maxn];
double val,all,now;
double tot[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
void find(int x,int sum){
    int maxx=0;
    vis[x]=stp,size[x]=1;
    for(int i=start[x];i;i=then[i])
        if(fin[to[i]]==0&&vis[to[i]]!=stp)
            find(to[i],sum),size[x]+=size[to[i]],maxx=max(maxx,size[to[i]]);
    maxx=max(maxx,sum-size[x]);
    if(maxx<minn)
        minn=maxx,pos=x;
}
void dfs(int x,int last,int dis,int top){
    now+=1.0*v[x]*dis*sqrt(dis),all+=1.5*v[x]*sqrt(dis),tot[top]+=1.5*v[x]*sqrt(dis);
    for(int i=start[x];i;i=then[i])
        if(to[i]!=last)
            dfs(to[i],x,dis+worth[i],top);
}
void solve(int x,int sum){
    stp++,minn=inf,find(x,sum),x=pos,fin[x]=1;
    all=now=0;
    for(int i=start[x];i;i=then[i])
        tot[to[i]]=0,dfs(to[i],x,worth[i],to[i]);
    if(now<val)
        val=now,ans=x;
    find(x,sum);
    for(int i=start[x];i;i=then[i])
        if(fin[to[i]]==0&&all-2*tot[to[i]]<0){
            solve(to[i],size[to[i]]);
            break;
        }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    val=1e30,solve(1,n);
    printf("%d %.10lf\n",ans,val);
    return 0;
}