题解：P10602 [CEOI 2009] Harbingers

· · 题解

双倍经验：P2305 [NOI2014] 购票

题解里竟然没有出栈序写法，我来写一篇。

首先列出朴素的 DP 式：

f_u=\min_{v \in pre_u} f_v+v_u(dis_u-dis_v)+w_u

拆开以后发现是个一次函数，直接李超树维护。

但是是链查，难道要树剖加树套树？3 个 \log 难以接受。

这里介绍一个 trick：出栈序，就是每个节点 \operatorname{dfs} 时出栈的时间戳。设时间戳为 T_i，如果 u 能直接到 v，那么直接查 [T_u,T_v] 就是对的，因为区间内不在路径上的点一定还没被更新到。

原题题解区没有对此给出说明，只是说画图可知。个人感性理解了一下，大概是因为按原顺序 \operatorname{dfs}，那么当前在的点一定是所有还没有更新的点中出栈序最小的，那么区间内不在路径上的点一定还没被更新到，所以直接查是正确的。

注意这道题要离散化横坐标（本人因为离散化写错调了半天）。

Code

#include"bits/stdc++.h"
#define re register
#define int long long
#define k(i) (-t[(i)].dis)
#define b(i) (f[(i)])
using namespace std;
const int maxn=1e6+10,inf=1e18;
int n,len,cnt,tim,tot,segcnt;
int v[maxn],w[maxn],head[maxn],f[maxn],c[maxn];
struct edge{
    int to,nxt,w;
}e[maxn<<1];
struct node{
    int dis,out;
}t[maxn];
struct lct{
    int ls,rs,id;
}tr[maxn<<1];
struct line{
    int k,b;
}lin[maxn];
struct tree{
    int rt;
}root[maxn<<2];
inline void add(int u,int v,int w){
    ++cnt;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline int calc(int x,int id){return lin[id].k*c[x]+lin[id].b;}
inline void dfs1(int u,int fa){
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        t[v].dis=t[u].dis+e[i].w;
        dfs1(v,u);
    }
    t[u].out=++tim;
}
inline void add(int x){
    ++tot;
    lin[tot].k=k(x);
    lin[tot].b=b(x);
}
inline void update(int l,int r,int id,int &p){
    if(!p) p=++segcnt;
    int mid=(l+r)>>1;
    if(calc(mid,id)<calc(mid,tr[p].id)) swap(id,tr[p].id);
    if(calc(l,id)<calc(l,tr[p].id)) update(l,mid,id,tr[p].ls);
    if(calc(r,id)<calc(r,tr[p].id)) update(mid+1,r,id,tr[p].rs);
}
inline void update(int l,int r,int pos,int id,int p){
    update(1,len,id,root[p].rt);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,pos,id,p<<1);
    else update(mid+1,r,pos,id,p<<1|1);
}
inline int query(int l,int r,int pos,int p){
    if(!p) return inf;
    int mid=(l+r)>>1;
    int res=calc(pos,tr[p].id);
    if(l==r) return res;
    if(pos<=mid) return min(res,query(l,mid,pos,tr[p].ls));
    else return min(res,query(mid+1,r,pos,tr[p].rs));
}
inline int query(int l,int r,int L,int R,int p,int pos){
    if(l>=L&&r<=R) return query(1,len,pos,root[p].rt);
    int mid=(l+r)>>1,res=inf;
    if(L<=mid) res=min(res,query(l,mid,L,R,p<<1,pos));
    if(R>mid) res=min(res,query(mid+1,r,L,R,p<<1|1,pos));
    return res;
}
inline void dfs(int u,int fa){
    if(u!=1) f[u]=query(1,n,t[u].out,t[1].out,1,v[u])+t[u].dis*c[v[u]]+w[u];
    add(u);
    update(1,n,t[u].out,tot,1);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1,u,v,w;i<n;++i) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
    for(re int i=2;i<=n;++i) cin>>w[i]>>v[i];
    for(re int i=0;i<=n;++i) lin[i].b=inf;
    for(re int i=1;i<n;++i) c[i]=v[i+1];
    sort(c+1,c+n-1+1);
    len=unique(c+1,c+n-1+1)-(c+1);
    for(re int i=2;i<=n;++i) v[i]=lower_bound(c+1,c+len+1,v[i])-c;
    dfs1(1,0);
    dfs(1,0);
    for(re int i=2;i<=n;++i) cout<<f[i]<<" ";
    return 0;
}