932F Escape Through Leaf

传送门

题目大意

https://www.luogu.org/problemnew/show/CF932F

分析

我们可以从叶子向根每次插入b和ans

所以我们不难发现就是相当于插入线段

于是李超树+线段树合并即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define int long long

const int maxm = 2e5;

const int M = 1e5;

struct node {

    int k,b,le,ri;

};

node d[];

int n,m,a[],b[],rt[],ans[],cnt,sum,Ans;

bool vis[];

vector<int>v[];

inline int get(int b1,int k1,int b2,int k2){return (b2-b1)/(k1-k2);}

inline void add(int le,int ri,int wh,int B,int K){

    if(!vis[wh]){

      d[wh].k=K;

      d[wh].b=B;

      vis[wh]=;

      return;

    }

    int f1=K*(le-M)+B,f2=d[wh].k*(le-M)+d[wh].b,f3=K*(ri-M)+B,f4=d[wh].k*(ri-M)+d[wh].b;

    if(f1>=f2&&f3>=f4)return;

    if(f1<=f2&&f3<=f4)d[wh].k=K,d[wh].b=B;

      else {

          int mid=(le+ri)>>;

          int x=get(B,K,d[wh].b,d[wh].k)+M;

          if(f1<=f2){

            if(x>mid)d[wh].ri=(d[wh].ri?d[wh].ri:++cnt),

                        add(mid+,ri,d[wh].ri,d[wh].b,d[wh].k),d[wh].k=K,d[wh].b=B;

              else d[wh].le=(d[wh].le?d[wh].le:++cnt),

                     add(le,mid,d[wh].le,B,K);

          }else {

            if(x<=mid)d[wh].le=(d[wh].le?d[wh].le:++cnt),

                       add(le,mid,d[wh].le,d[wh].b,d[wh].k),d[wh].k=K,d[wh].b=B;

              else d[wh].ri=(d[wh].ri?d[wh].ri:++cnt),

                     add(mid+,ri,d[wh].ri,B,K);

          }

      }

}

inline void que(int le,int ri,int wh,int x){

    if(!wh)return;

    if(vis[wh])Ans=min(Ans,(x-M)*d[wh].k+d[wh].b);

    if(le==ri)return;

    int mid=(le+ri)>>;

    if(mid>=x)que(le,mid,d[wh].le,x);

      else que(mid+,ri,d[wh].ri,x);

}

inline int mer(int le,int ri,int x,int y){

    if(!x||!y)return x+y;

    int mid=(le+ri)>>;

    d[x].le=mer(le,mid,d[x].le,d[y].le);

    d[x].ri=mer(mid+,ri,d[x].ri,d[y].ri);

    add(le,ri,x,d[y].b,d[y].k);

    return x;

}

inline void dfs(int x,int fa){

    for(int i=;i<v[x].size();i++)

      if(v[x][i]!=fa){

          dfs(v[x][i],x);

          rt[x]=mer(,maxm,rt[x],rt[v[x][i]]);

      }

    Ans=1000000000000000007ll;

    if(!rt[x])rt[x]=++cnt;

    que(,maxm,rt[x],a[x]+M);

    if(v[x].size()==&&v[x][]==fa)Ans=;

    ans[x]=Ans;

    add(,maxm,rt[x],ans[x],b[x]);

}

signed main(){

    int i,j,k;

    scanf("%lld",&n);

    for(i=;i<=n;i++)scanf("%lld",&a[i]);

    for(i=;i<=n;i++)scanf("%lld",&b[i]);

    for(i=;i<n;i++){

      int x,y;

      scanf("%lld%lld",&x,&y);

      v[x].push_back(y);

      v[y].push_back(x);

    }

    for(i=;i<;i++)d[i].le=d[i].ri=d[i].k=d[i].b=;

    dfs(,);

    for(i=;i<=n;i++)printf("%lld ",ans[i]);

    return ;

}