题解归档 - cf932F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932F
• 本地来源：problems/cf932F/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/F
• 原始标题：CF932F Escape Through Leaf

思路

CF932F Escape Through Leaf

题意

根为 1 的树，点 (i) 有权值 (a_i,b_i)。从 (x) 跳到子树内 (y) 代价 (a_x\cdot b_y)，路径代价为跳跃代价之和。对每个点求到任意叶子的最小代价；根即使度数为 1 也不算叶子。

做法

树形 DP：

[
dp_u=\min_{v\in subtree(u),\,v\ne u}(a_u\cdot b_v+dp_v),\quad \text{叶子 }dp=0
]

把 (dp_v + a_u\cdot b_v) 看成直线 (f_v(x)=b_v\cdot x+dp_v)，在 (x=a_u) 处取最小值 → 李超线段树维护子树直线集。

启发式合并（按 cccc 大小 swap）：小集合并入大集合，逐条 add 进李超树。DFS 后：

1. 非叶子：dp[u]=query(a[u])
2. 插入直线 ((b_u,dp_u))

复杂度 (O(n\log^2 n))。

Catalog

• 标签：Li Chao tree
• AC 后沉淀：lib/数据结构(LiChao树).cpp

本地

• 样例：python tools/run_exe.py cf932F --input problems/cf932F/sample.in
• 对拍：python tools/stress.py cf932F -n 500

代码

来源：problems/cf932F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
const ll maxn=100005;
const ll maxa=200005;
vector<ll>ss[maxn];
ll a[maxn],b[maxn],dp[maxn],n,i,j,k;
struct Line{
    ll m,c;
    Line(){m=0,c=inf;}
    Line(ll k,ll b){m=k,c=b;}
    ll vl(ll x){return m*x+c;}
};
struct lichao{
    ll tl,tr,tm;
    Line val;
    lichao *l,*r;
    lichao(ll x,ll y){
        tl=x,tr=y,tm=tl+(tr-tl)/2;
        l=r=nullptr;
    }
    void add(Line u){
        if(u.vl(tm)<val.vl(tm)) swap(u,val);
        if(u.vl(tl)<val.vl(tl)){
            if(l==nullptr) l=new lichao(tl,tm);
            l->add(u);
        }
        if(u.vl(tr)<val.vl(tr)){
            if(r==nullptr) r=new lichao(tm+1,tr);
            r->add(u);
        }
    }
    ll query(ll x){
        ll ans=val.vl(x);
        if(x<=tm){
            if(l!=nullptr) ans=min(ans,l->query(x));
        }else if(r!=nullptr) ans=min(ans,r->query(x));
        return ans;
    }
};
vector<Line>cccc[maxn];
lichao *tr[maxn];
void dfs(ll x,ll fa){
    ll zc,pd=1;
    tr[x]=new lichao(-maxa,maxa);
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa) continue;
        pd=0;
        dfs(zc,x);
        if(cccc[zc].size()>cccc[x].size()){
            swap(cccc[x],cccc[zc]);
            swap(tr[x],tr[zc]);
        }
        ll p;
        for(p=0;p<(ll)cccc[zc].size();p++){
            tr[x]->add(cccc[zc][p]);
            cccc[x].push_back(cccc[zc][p]);
        }
    }
    if(pd) dp[x]=0;
    else dp[x]=tr[x]->query(a[x]);
    Line cur=Line(b[x],dp[x]);
    cccc[x].push_back(cur);
    tr[x]->add(cur);
}
int main(){
    ll x,y;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    for(i=1;i<=n-1;i++){
        cin>>x>>y;
        ss[x].push_back(y);
        ss[y].push_back(x);
    }
    dfs(1,0);
    for(i=1;i<=n;i++){
        if(i>1) cout<<" ";
        cout<<dp[i];
    }
    cout<<"\n";
    return 0;
}