CF932F Escape Through Leaf

设 \(f_x\) 表示点 \(x\) 到叶子节点的最优答案。

考虑 \(x\) 下一步跳到点 \(y\)，可以得到转移方程为

将 \(f_y\) 看作 \(b\)，将 \(a_x\) 看作 \(x\)，将 \(b_y\) 看作 \(k\)，则式子的右边为多条直线，而要求的答案是直线在 \(x=a_x\) 处最小值。

考虑使用李超线段树维护直线的下凸壳（因为求的是 \(\min\)），对于一个节点 \(x\)，先从子节点中转移当前点的 \(f_x\)，再将子节点全部合并并插入当前节点的直线。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 200005
#define Dt 100005
#define Maxn 200010
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int n,head[N],cnt,idx;
ll ans[N],a[N],b[N];
struct line{
	ll k,b;
}l[N];
inline ll calc(int id,int x){
	return l[id].k*x+l[id].b;
}
struct edge{
	int v,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
int rt[N*25];
struct node{
	int s,ls,rs;
}t[N*25];
#define lc(x) t[x].ls
#define rc(x) t[x].rs
#define s(x) t[x].s
inline void update(int &x,int l,int r,int num){
	if(!x) return x=++idx,s(x)=num,void();
	int mid=l+r>>1;
	if(calc(s(x),mid)>calc(num,mid)) swap(s(x),num);
	if(calc(s(x),l)>calc(num,l)) update(lc(x),l,mid,num);
	if(calc(s(x),r)>calc(num,r)) update(rc(x),mid+1,r,num);	
}
inline ll query(int &x,int l,int r,int num){
	if(!x) return inf;
	int mid=l+r>>1;
	ll res=calc(s(x),num);
	if(num<=mid) res=min(res,query(lc(x),l,mid,num));
	else res=min(res,query(rc(x),mid+1,r,num));
	return res;
}
inline int merge(int x,int y,int l,int r){
	if(!x||!y) return x|y;
	int mid=l+r>>1;
	update(x,l,r,s(y));//把y的信息插入x
	lc(x)=merge(lc(x),lc(y),l,mid);
	rc(x)=merge(rc(x),rc(y),mid+1,r);
	return x; 
}
inline void dfs(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		rt[x]=merge(rt[x],rt[v],1,Maxn);
	}
	ans[x]=query(rt[x],1,Maxn,a[x]+Dt);
	if(ans[x]==inf) ans[x]=0;
	l[x]=(line){b[x],ans[x]-b[x]*Dt};
	update(rt[x],1,Maxn,x);
}
int main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	for(int i=1,u,v;i<n;i++) read(u,v),add(u,v),add(v,u);
	dfs(1,0);
	for(int i=1;i<=n;i++) put(' ',ans[i]);
	return 0;
}