题解 CF932F 【Escape Through Leaf】

s_y_z_r_y · 2020-05-28 19:35:03 · 题解

发现洛谷题解只有李超线段树和平衡树维护凸壳，但是这也可以用点分治做。

设 f_i 表示从 i 出发到达子树内的叶子的最小花费。那么有转移方程

考虑用斜率优化这个 dp式子。下面是我的优化方式，和这道题里面其他题解的优化方式不太一样，如果知道怎么斜率优化可以跳过不看。

设 j ， k 是 i 子树内的点，且 b_k>b_j ， f_i 从 j 点转移。那么有不等式

设 j 代表的点为 (b_j,f_j) ，最后的不等式的意思是 当 j 点和 k 点的连线的斜率大于 -a_i 时，用 j 点转移会更优。于是可以维护一个下凸壳然后做了。

点分治时要注意这是有根树，每次处理完 当前联通块的重心 的 子树节点 后，再拿它们来更新 重心以及它在这个联通块里的祖先。因为不保证子树节点的 b_j 递增，所以还要排个序。被更新的 重心和祖先节点 我也以 a_i 为关键字排序了一遍，不过也可以二分凸壳，反正时间复杂度都一样。

点分治一个 log，排序一个 log，总时间复杂度 O(nlog^2n)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double db;
const db eps=1e-16;
const db maxn=1e21;
#define M 100005
#define pb push_back

template <class T>
inline void rd(T &x) {
    x=0; char c=getchar(); int f=1;
    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}

int al[M<<1],cl[M<<1],tp[M],ttp;
int Al,rt,sz[M],fa[M],vis[M];
int sl[M];
int qe[M];
ll A[M],B[M];
ll dp[M];
vector<int> G[M];

int Mx(int x,int y){ return x>y?x:y; }
db xian(int x,int y){
    if(B[x]==B[y]) return dp[x]<=dp[y]?maxn:-maxn;
    return (dp[x]-dp[y])/(db)(B[x]-B[y]);
}
int cmp(db x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
bool cmp2(int x,int y){ if(B[x]==B[y]) return dp[x]>dp[y]; return B[x]<B[y]; }
bool cmp3(int x,int y){ return A[x]>A[y]; }

void dfs(int x,int f){
    int v,t=1;
    fa[x]=f;
    for(int i=tp[x];i;i=cl[i]) if((v=al[i])!=f){
        dfs(v,x);
        t=0;
    }
    if(t) dp[x]=0;
}

void fin_rt(int x,int f){
    int v,mx=0;
    sz[x]=1;
    for(int i=tp[x];i;i=cl[i]) if((!vis[v=al[i]]) && v!=f){
        fin_rt(v,x);
        mx=Mx(mx,sz[v]);
        sz[x]+=sz[v];
    }
    mx=Mx(mx,Al-sz[x]);
    if(mx<=(Al>>1)) rt=x;
}

void get_G(int x,int f){
    int v;
    G[rt].pb(x);
    for(int i=tp[x];i;i=cl[i]) if((!vis[v=al[i]])&&v!=f) get_G(v,x);
}

void sol(int x,int siz){
    if(siz==1) return (void)(vis[x]=1);
    Al=siz;
    fin_rt(x,fa[x]);
    int f=rt,q,ct=0,op=0,ed=0;

    vis[f]=1;
    for(int i=tp[f];i;i=cl[i]) if(al[i]!=fa[f]) get_G(al[i],f);
    for(int i=tp[f];i;i=cl[i]) if(al[i]!=fa[f]) siz-=sz[al[i]],sol(al[i],sz[al[i]]);
    for(int i=f;i!=fa[x];i=fa[i]) sl[++ct]=i;
    if(!G[f].empty()) sort(G[f].begin(),G[f].end(),cmp2);

    for(int v:G[f]){
        while(ed>1 && cmp(xian(qe[ed-1],qe[ed-2]) - xian(qe[ed-1],v)) >=0) --ed;
        if((!ed) || B[v]!=B[qe[ed-1]]) qe[ed++]=v;
        else if(dp[v]<dp[qe[ed-1]]) qe[ed-1]=v;
    }

    if(ct){
        sort(sl+1,sl+1+ct,cmp3);
        for(int i=1;i<=ct;++i){
            q=sl[i];
            while(op<ed-1 && cmp(xian(qe[op],qe[op+1]) + A[q]) <=0) ++op;
            dp[q]=min(dp[q],dp[qe[op]]+A[q]*B[qe[op]]);
        }
    }

    vis[f]=0;
    for(int i=tp[f];i;i=cl[i]) if(al[i]!=fa[f]) vis[al[i]]=1;
    G[f].clear();
    sol(x,siz);
}

void link(int x,int y){ al[++ttp]=y; cl[ttp]=tp[x]; tp[x]=ttp; }

int main(){
    int n,t,x,y;
    ll v;
    rd(n);
    for(int i=1;i<=n;++i) rd(A[i]);
    for(int i=1;i<=n;++i) rd(B[i]);
    for(int i=2;i<=n;++i){
        rd(x); rd(y);
        link(x,y);
        link(y,x);
    }
    memset(dp,127,sizeof(dp));
    dfs(1,0);
    sol(1,n);
    for(int i=1;i<=n;++i) printf("%lld ",dp[i]);
    puts("");
    return 0;
}