Kattis yatp(斜率优化+树分治)

题意:
2e5个点的无根树，每个点有点权，每条边有边权，定义一条简单路径的花费=这条路径两个端点点权的乘积+边权和，
（一条简单路径可以包含一个点，这样花费是该点权的平方），最后问从每个点出发的最小花费

思路:
ans[i]=min(a[i]*a[j]+d[i]+d[j])
->y=-a[i]*x+ans[i]
有三个点X,Y,Z,现在要求X的答案
假设Y比Z更优,
则X*Y+(X到根的边权和+Y到根的边权和)<=X*Z+(X到根的边权和+Z到根的边权和)
->X<=(Z到根的边权和-Y到根的边权和)/(Y-Z)(假设Y大于Z)

需要注意的一点就是如果两个点在重心的同一个子树中,那么这个时候这两个点之间不需要特殊处理

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
struct Edge{
    int to,next;
    long long w;
}e[N*2];
long long a[N],ans[N];
int size[N],Count,root,f[N],head[N],tot;
bool Del[N];

void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}

void addedge(int from,int to,long long w){
    e[tot]=(Edge){to,head[from],w};
    head[from]=tot++;
}

void getroot(int u,int pre){
    f[u]=0,size[u]=1;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(v==pre||Del[v])  continue;
        getroot(v,u);
        size[u]+=size[v];
        f[u]=max(f[u],size[v]);
    }
    f[u]=max(f[u],Count-size[u]);
    if(f[u]<f[root])    root=u;
}

struct node{
    int id;
    long long v,w;
}b[N];
vector<int>tmp;
long long X[N],Y[N];

bool cmp(const node& x,const node& y){
    if(x.v==y.v)    return x.w<y.w;
    else    return x.v<y.v;
}

long long getUP(int x,int y){
    return Y[x]-Y[y];
}

long long getDown(int x,int y){
    return X[x]-X[y];
}

int q[N],TOT;

void getdeep(int u,int pre,long long w){
    b[++TOT]=(node){u,a[u],w};
    X[u]=a[u],Y[u]=w;
    tmp.push_back(u),size[u]=1;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(v==pre||Del[v]) continue;
        getdeep(v,u,w+e[i].w);
        size[u]+=size[v];
    }
}

long long getDP(int x,int y){
    return X[x]*X[y]+Y[x]+Y[y];
}

bool cmp1(const int& u,const int& v){
    return a[u]>a[v];
}

void work(int u){
    Del[u]=true;
    TOT=0,tmp.clear();
    tmp.push_back(u);
    b[++TOT]=(node){u,a[u],0};
    X[u]=a[u],Y[u]=0;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(!Del[v])
            getdeep(v,u,e[i].w);
    }
    sort(b+1,b+TOT+1,cmp);
    sort(tmp.begin(),tmp.end(),cmp1);
    int nn=1;
    for(int i=2;i<=TOT;i++)
        if(b[i].v!=b[nn].v&&b[i].w<b[nn].w)    b[++nn]=b[i];
    int Head=0,tail=0;
    for(int i=1;i<=nn;i++){
        while(Head+1<tail&&getUP(b[i].id,q[tail-1])*getDown(q[tail-1],q[tail-2])<=getUP(q[tail-1],q[tail-2])*getDown(b[i].id,q[tail-1]))
            tail--;
        q[tail++]=b[i].id;
    }
    for(int i=0;i<TOT;i++){
        while(Head+1<tail&&getUP(q[Head+1],q[Head])<=-a[tmp[i]]*getDown(q[Head+1],q[Head]))
            Head++;
        long long Tmp=getDP(tmp[i],q[Head]);
        if(ans[tmp[i]]==-1) ans[tmp[i]]=Tmp;
        else    ans[tmp[i]]=min(ans[tmp[i]],Tmp);
    }
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(!Del[v]){
            Count=f[0]=size[v];
            getroot(v,root=0);
            work(root);
        }
    }
}

int main(){
    int u,v,n;
    long long w;
    while(scanf("%d",&n)!=EOF){
        init();
        for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
        for(int i=1;i<n;i++){
            scanf("%d%d%lld",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        Count=f[0]=n;
        memset(Del,false,sizeof(Del));
        getroot(1,root=0);
        memset(ans,-1,sizeof(ans));
        work(root);
        long long Ans=0;
        for(int i=1;i<=n;i++)
            Ans+=ans[i];
        printf("%lld\n",Ans);
    }
    return 0;
}