题解：P10602 [CEOI 2009] Harbingers

Lucyna_Kushinada · 2025-09-13 19:59:28 · 题解

近乎是可撤销李超线段树的板子了，题目本身没什么思维含量。

其中 A 表示 i 的祖先集合。

容易发现是一个斜率优化的形式，变换一下转移式。

深搜天然就满足一个栈的结构，在第一次访问某个节点的时候入栈，访问完该节点子树后出栈。

那么对于某时刻，栈内存储的那些点就是当前所在点的所有祖先。

所以动态维护一个基于栈的可撤销李超树，然后进行转移即可。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 102509
#define int long long

const int inf=2e9;
int n,f[N],w[N],v[N],d[N],len;
vector<int>vec;

struct edge{
    int t,w;
};

vector<edge>e[N];

struct ln{
    int k,b,i;
};

inline int get(int x){
    return lower_bound(all(vec),x)-bg(vec)+1;
}

struct lct{
    #define mid ((l+r)>>1)

    int tp;
    pair<ln,int>st[N<<5];
    ln tr[N<<2];

    inline void build(int k,int l,int r){
        tr[k]={inf,inf<<20,0};

        if(l==r){
            return;
        }

        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
    }

    inline int calc(ln u,int x){
        return u.k*x+u.b;
    }

    inline bool cmp(ln u,ln v,int x){
        return calc(u,x)<calc(v,x);
    }

    inline void ref(int k,int l,int r,ln u){
        ln &v=tr[k];

        if(cmp(u,v,vec[mid-1])){
            st[++tp]={v,k};
            swap(u,v);
        }

        if(l==r){
            return;
        }

        if(cmp(u,v,vec[l-1])){
            ref(k*2,l,mid,u);
        }

        if(cmp(u,v,vec[r-1])){
            ref(k*2+1,mid+1,r,u);
        }
    }

    inline void recall(int ed){
        while(tp>ed){
            tr[st[tp].se]=st[tp].fi;
            tp--;
        }
    }

    inline ln ask(int k,int l,int r,int x){
        if(l==r){
            return tr[k];
        }

        ln ans=tr[k];

        if(x<=mid){
            ln re=ask(k*2,l,mid,x);

            if(cmp(re,ans,vec[x-1])){
                ans=re;
            }
        }
        else{
            ln re=ask(k*2+1,mid+1,r,x);

            if(cmp(re,ans,vec[x-1])){
                ans=re;
            }
        }

        return ans;
    }

    #undef mid
}t;

inline void dfs(int k,int fa){
    if(k!=1){
        ln u=t.ask(1,1,len,get(v[k]));

        f[k]=d[k]*v[k]+w[k]+t.calc(u,v[k]);
    }

    int now=t.tp;

    t.ref(1,1,len,(ln){-d[k],f[k],k});

    for(edge x:e[k]){
        if(x.t==fa){
            continue;
        }

        d[x.t]=d[k]+x.w;

        dfs(x.t,k);
    }

    t.recall(now);
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;

    rep(i,1,n-1){
        int u,v,w;
        cin>>u>>v>>w;

        e[u].pb({v,w});
        e[v].pb({u,w});
    }

    rep(i,2,n){
        cin>>w[i]>>v[i];
    }

    rep(i,1,n){
        vec.pb(v[i]);
    }

    sort(all(vec));
    vec.erase(unique(all(vec)),ed(vec));

    len=sz(vec);

    t.build(1,1,len);

    dfs(1,0);

    rep(i,2,n){
        cout<<f[i]<<' ';
    }

    return 0;
}