[BZOJ]3672: [Noi2014]购票

Time Limit: 30 Sec Memory Limit: 512 MB

Description

　　今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。

　　全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 f_v 以及到父亲城市道路的长度 s_v。

　　从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。

　　对于任意一个城市 v，我们会给出一个交通工具的距离限制 l_v。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 l_v 时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 p_v,q_v 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dp_v+q_v。

　　每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

Input

　　第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。

Output

　　输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。

Sample Input

　　7 3
　　1 2 20 0 3
　　1 5 10 100 5
　　2 4 10 10 10
　　2 9 1 100 10
　　3 5 20 100 10
　　4 4 20 0 10

Sample Output

　　40
　　150
　　70
　　149
　　300
　　150

HINT

　　对于所有测试数据，保证 0≤p_v≤10⁶，0≤q_v≤10¹²，1≤f_v<v；保证 0<s_v≤l_v≤2×10¹¹，且任意城市到SZ市的总路程长度不超过 2×10¹¹。

　　输入的 t 表示数据类型，0≤t<4，其中：

　　当 t=0 或 2 时，对输入的所有城市 v，都有 f_v=v-1，即所有城市构成一个以SZ市为终点的链；

　　当 t=0 或 1 时，对输入的所有城市 v，都有 l_v=2×10¹¹，即没有移动的距离限制，每个城市都能到达它的所有祖先；

　　当 t=3 时，数据没有特殊性质。

　　n=2×10^5

Solution

　　此题有很妙的树分治解法，但我觉得还不如我的树套树解法容易实现，于是我就大力树套树了。

　　容易得出DP方程f[i]=max(f[j]+p[i]*(d[i]-d[j])+q[i])，其中j是i的祖先，d[i]-d[j]<=l[i]，d[i]表示i到根的距离，考虑斜率优化，得出i从j转移优于从k转移（d[j]>d[k]）的条件是(f[j]-f[k])/(d[j]-d[k])<p[i]，对每个点，我们可以把能转移到它的点按深度顺序加入凸壳中，维护斜率单调上升，然后拿p[i]进去二分就能找到最优转移点，考虑用数据结构维护这个过程，从根开始向下dfs，用无旋treap维护把当前dfs到的点到根路径上的所有点依次加入得到的凸壳，插入的时候直接把多余的点split出来，撤销的时候把之前split出来的直接merge回去就能保证复杂度，由于转移有深度限制，我们用线段树套treap，每次二分一下最远的转移点然后去线段树上查就好了，复杂度O(nlogn^2)。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
inline ll read()
{
    ll x;char c;
    while((c=getchar())<'0'||c>'9');
    for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
    return x;
}
#define MN 200000
#define N 262144
#define ND 4000000
struct edge{int nx,t;}e[MN+5];
int h[MN+5],en,fa[MN+5],p[MN+5],z[MN+5],zn,Tn;
ll d[MN+5],q[MN+5],lm[MN+5],f[MN+5];
inline void insEdge(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
struct treap
{
    treap*l,*r;int p;ll f,d;double x;
    inline int ran()
    {
        static int x=23333;
        return x^=x<<13,x^=x>>17,x^=x<<5;
    }
    treap(ll f=0,ll d=0,double x=0):f(f),d(d),x(x){l=r=0;p=ran();}
}*t[N*2+5],T[ND+5];
vector<treap*> v[MN+5];
treap*merge(treap*a,treap*b)
{
    if(!a)return b;if(!b)return a;
    if(a->p>b->p)return a->r=merge(a->r,b),a;
    return b->l=merge(a,b->l),b;
}
void query(treap*k,int x)
{
    if(!k)return;
    f[x]=min(f[x],k->f+p[x]*(d[x]-k->d)+q[x]);
    query(k->x<p[x]?k->r:k->l,x);
}
void split(treap*k,int x,treap*&a,treap*&b)
{
    if(!k){a=b=0;return;}
    if((f[x]-k->f)/(d[x]-k->d)<k->x)split(k->l,x,a,k->l),b=k;
    else split(k->r,x,k->r,b),a=k;
}
void query(int l,int r,int x)
{
    for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)query(t[l+1],x);
        if( r&1)query(t[r-1],x);
    }
}
void ins(int k,int x)
{
    for(k+=N;k;k>>=1)
    {
        treap*p;
        split(t[k],x,t[k],p);
        v[x].push_back(p);
        if(t[k])
        {
            for(p=t[k];p->r;)p=p->r;
            double s=(f[x]-p->f)/(d[x]-p->d);
            T[++Tn]=treap(f[x],d[x],s);
        }
        else T[++Tn]=treap(f[x],d[x],-1e18);
        t[k]=merge(t[k],T+Tn);
    }
}
void del(int k,int x)
{
    int i=0;
    for(k+=N;k;k>>=1)
    {
        treap**p;
        for(p=t+k;(*p)->r;p=&((*p)->r));
        *p=(*p)->l;
        t[k]=merge(t[k],v[x][i++]);
    }
}
void dfs(int x)
{
    if(x==1)f[x]=0;
    else
    {
        int l=1,r=zn,mid,s;
        while(l<=r)
            if(d[x]-d[z[mid=l+r>>1]]<=lm[x])s=mid,r=mid-1;
            else l=mid+1;
        query(s,zn,x);
    }
    z[++zn]=x;ins(zn,x);
    for(int i=h[x];i;i=e[i].nx)dfs(e[i].t);
    del(zn,x);--zn;
}
int main()
{
    int n,i;
    n=read();read();
    for(i=2;i<=n;++i)
    {
        insEdge(fa[i]=read(),i);d[i]=d[fa[i]]+read();
        p[i]=read();q[i]=read();lm[i]=read();
    }
    memset(f,127,sizeof(f));
    dfs(1);
    for(i=2;i<=n;++i)printf("%lld
",f[i]);
}