NOI2014 购票

本文移植自个人的原博客（原文）

题目链接

UOJ 7

题目描述

题解

设$f_x$表示从$x$到根节点的最小花费，易得动态规划方程为:

$$f_x=min(f_y+(d_x-d_y) * p_x+q_x)$$

容易观察到该方程具有决策单调性，当x从k转移优于从j转移时推得斜率方程为：

$$(f_k-f_j)/(d_k-d_j) < p_x$$

此处便可以通过树分治来计算答案，由于在更新$f_x$时其所有父亲节点都已经处理，所以得到重心后，应先递归深度小的部分，然后处理当前分治结构，再递归深度大的部分。

对于当前分治结构，应计算重心的所有父亲节点对于子树的贡献（即父亲节点要加入单调栈），考虑到$l_x$的限制，我们可以将需要更新的节点按其所能达到的最浅深度从大到小排序，这样处理不会对单调栈要求删除操作，在得到更新的单调栈后，在凸包上根据斜率方程二分即可得到答案。需要注意由于此处并没有计算重心的贡献，需要特别处理一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 2e5+1;
const ll inf = 2e15;
int fa[N],n,tp,head[N],cnt;
int sz[N],mx[N],tot,rt,q[N],qq[N];
ll p1[N],q1[N],w[N],l[N],d[N],f[N];
bool vis[N];

struct nd{
    int ne,to,w;
}e[N*2];

void in(int x,int y,ll w){
    e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;
}

bool cmp(int x,int y){
    return l[x]>l[y];
}

void getrt(int x,int f){
    sz[x]=1;mx[x]=0;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=f&&!vis[e[i].to]){
        int y=e[i].to;
        getrt(y,x);
        sz[x]+=sz[y];
        mx[x]=max(mx[x],sz[y]);
    }
    mx[x]=max(mx[x],tot-sz[x]);
    if(mx[x]<mx[rt])rt=x;
}

void dfs1(int x,int f){
    sz[x]=1;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=f&&!vis[e[i].to]){
        dfs1(e[i].to,x);
        sz[x]+=sz[e[i].to];
    }
}

void dfs2(int x,int f){
    q[++q[0]]=x;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=f&&!vis[e[i].to]){
        dfs2(e[i].to,x);
    }
}

db k(int x,int y){
    return (db)(f[x]-f[y])/(d[x]-d[y]);
}

void CDQ(int y,int x){
    dfs1(x,-1);
    vis[x]=1;
    if(x!=1&&!vis[fa[x]]){
        tot=sz[fa[x]];
        rt=0;
        getrt(fa[x],-1);
        CDQ(y,rt);
    }
    q[0]=0;dfs2(x,fa[x]);
    sort(q+1,q+q[0]+1,cmp);
    int top=0;
    for(int i=1,now=fa[x];i<=q[0];++i){
        while(now!=fa[y]&&l[q[i]]<=d[now]){
//            if(!now)break;
            while(top>1&&k(qq[top-1],qq[top])<=k(qq[top],now))top--;
            qq[++top]=now;now=fa[now];
        }
        if(!top)continue;
        int l=1,r=top;
        while(l!=r){
            int mid=l+r>>1;
            if(k(qq[mid],qq[mid+1])<p1[q[i]])r=mid;
            else    l=mid+1;
        }
        int j=q[i];
        f[j]=min(f[j],f[qq[l]]+(d[j]-d[qq[l]])*p1[j]+q1[j]);
    }
    for(int i=1;i<=q[0];++i)
    if(q[i]!=x&&l[q[i]]<=d[x]){
        int j=q[i];
        f[j]=min(f[j],f[x]+(d[j]-d[x])*p1[j]+q1[j]);
    }
    for(int i=head[x];i;i=e[i].ne)
    if(!vis[e[i].to]&&e[i].to!=fa[x]){
        tot=sz[e[i].to];
        rt=0;
        getrt(e[i].to,x);
        CDQ(e[i].to,rt);
    }
}
int main(){
//    freopen("ex_ticket2.in","r",stdin);
//    freopen("ex_ticket2.out","w",stdout);
    mx[0]=1e9;
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    scanf("%d%d",&n,&tp);
    for(int i=2;i<=n;++i){
        scanf("%d%lld%lld%lld%lld",&fa[i],&w[i],&p1[i],&q1[i],&l[i]);
        in(fa[i],i,w[i]);in(i,fa[i],w[i]);
        d[i]=d[fa[i]]+w[i];
    }
    for(int i=2;i<=n;++i)l[i]=d[i]-l[i];
    tot=n;
    getrt(1,-1);
    CDQ(1,rt);
    for(int i=2;i<=n;++i)printf("%lld\n",f[i]);
}