C122 李超树合并+DP CF932F Escape Through Leaf

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ll long long
#define N 100005
#define INF 0x3f3f3f3f3f3f3f3f
#define mid ((l + r) >> 1)

int h[N], to[N << 1], ne[N << 1], idx;
inline void add(int x, int y) {
  ne[++idx] = h[x], to[idx] = y, h[x] = idx;
}
struct line {
  ll k, b;
} p[N];
int rt[N], tot, ls[N << 5], rs[N << 5], id[N << 5];
ll n, a[N], b[N], f[N];

ll Y(int i, ll x) { //求Y值
  return p[i].k * (x - N) + p[i].b; //x-N:修正
}
void change(int &u, int l, int r, int i) { //修改
  if (!u) { id[u = ++tot] = i; return; }
  if (Y(i, mid) < Y(id[u], mid)) swap(i, id[u]);
  if (Y(i, l) < Y(id[u], l)) change(ls[u], l, mid, i);
  if (Y(i, r) < Y(id[u], r)) change(rs[u], mid + 1, r, i);
}
ll query(int u, int l, int r, ll x) { //查询
  if (!u) return INF;
  ll ans = Y(id[u], x);
  if (x <= mid) return min(ans, query(ls[u], l, mid, x));
  else return min(ans, query(rs[u], mid + 1, r, x));
}
void merge(int &x, int y, int l, int r) { //合并
  if (!x || !y) { x = x | y; return; }
  merge(ls[x], ls[y], l, mid);
  merge(rs[x], rs[y], mid + 1, r);
  change(x, l, r, id[y]);  //插入直线id[y]
}
void dfs(int x, int fa) { //递归合并
  for (int i = h[x]; i; i = ne[i]) {
    int y = to[i];
    if (y == fa) continue;
    dfs(y, x);
    merge(rt[x], rt[y], 1, N << 1);
  }
  f[x] = query(rt[x], 1, N << 1, a[x] + N);
  if (f[x] == INF) f[x] = 0; //修正叶子节点
  p[x] = {b[x], f[x]};
  change(rt[x], 1, N << 1, x); //插入直线x
}
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; ++i) scanf("%lld", &b[i]);
  for (int i = 1, x, y; i < n; ++i)
    scanf("%d%d", &x, &y), add(x, y), add(y, x);
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) printf("%lld ", f[i]);
  return 0;
}

C122 李超树合并+DP CF932F Escape Through Leaf

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ll long long
#define N 100005
#define INF 0x3f3f3f3f3f3f3f3f
#define mid ((l+r)>>1)

int h[N],to[N<<1],ne[N<<1],idx;
inline void add(int x,int y){
  ne[++idx]=h[x],to[idx]=y,h[x]=idx;
}
struct line{
  ll k,b;
}p[N];
int rt[N],tot,ls[N<<5],rs[N<<5],id[N<<5];
ll n,a[N],b[N],f[N];

ll Y(int i,ll x){ //求Y值
  return p[i].k*(x-N)+p[i].b; //x-N:修正
}
void change(int &u,int l,int r,int i){ //修改
  if(!u){id[u=++tot]=i; return;}
  if(Y(i,mid)<Y(id[u],mid)) swap(i,id[u]);
  if(Y(i,l)<Y(id[u],l)) change(ls[u],l,mid,i);
  if(Y(i,r)<Y(id[u],r)) change(rs[u],mid+1,r,i);
}
ll query(int u,int l,int r,ll x){ //查询
  if(!u) return INF;
  ll ans=Y(id[u],x);
  if(x<=mid)return min(ans,query(ls[u],l,mid,x));
  else return min(ans,query(rs[u],mid+1,r,x));
}
void merge(int &x,int y,int l,int r){ //合并
  if(!x||!y){x=x|y; return;}
  merge(ls[x],ls[y],l,mid);
  merge(rs[x],rs[y],mid+1,r);
  change(x,l,r,id[y]);  //插入直线id[y]
}
void dfs(int x,int fa){ //递归合并
  for(int i=h[x];i;i=ne[i]){
    int y=to[i];
    if(y==fa) continue;
    dfs(y,x);
    merge(rt[x],rt[y],1,N<<1);
  }
  f[x]=query(rt[x],1,N<<1,a[x]+N);
  if(f[x]==INF) f[x]=0; //修正叶子节点
  p[x]={b[x],f[x]};
  change(rt[x],1,N<<1,x); //插入直线x
}
int main(){
  scanf("%lld",&n);
  for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
  for(int i=1;i<=n;++i)scanf("%lld",&b[i]);
  for(int i=1,x,y;i<n;++i)
    scanf("%d%d",&x,&y),add(x,y),add(y,x);
  dfs(1,0);
  for(int i=1;i<=n;++i)printf("%lld ",f[i]);
  return 0;
}