[DP记录]P2305 [NOI2014]购票

· · 个人记录

题意 :

给出一颗根为1的树,有边权,每个点向祖先走的代价是距离的一次函数,超出一定范围不能走(函数参数与范围均由起点给出)

问每个点到根的最小代价。

设F[u]为u点的答案,dep[u]为u点的深度。

F[v]\rightarrow F[u]=F[v]+P[u](dep[u]-dep[v])+Q[u] =F[v]-P[u]dep[v]+Q[u]+P[u]dep[u]

后面的Q[u]+P[u]dep[u]是有关目标点的常数。

每个候选决策可以表示为一条k=-dep[v];b=F[v]的直线,每次代入P[u]求值。

现在来考虑距离限制。

使用树上CDQ分治(点分治),每次找出当前分治块的重心,就把树分成了若干连通块。

与根相连的一部分优先分治处理,得到dp值。

然后处理跨越重心的贡献,我们把下方子树的节点按照lim-dep升序排序(即可以往重心祖先方向延伸多长)

贡献的时候,根据lim的限制向上加入直线(不要超出当前分治块),由于排过序lim单调,这样就不用删除了。

斜率也是单调的,那么单调队列维护凸包即可。

询问的x坐标不单调,需要在凸包上二分,考虑清楚边界情况。

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define eps 1e-12
#define MaxN 200500
using namespace std;
inline ll read()
{
  register ll X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
bool vis[MaxN];
vector<int> g[MaxN];
int rt,sum,siz[MaxN],maxp[MaxN];
void cnt(int u,int fa)
{
  sum++;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=fa&&!vis[v])
      cnt(v,u);
}
void getrt(int u,int fa)
{
  siz[u]=1;maxp[u]=0;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=fa&&!vis[v]){
      getrt(v,u);
      siz[u]+=siz[v];
      maxp[u]=max(maxp[u],siz[v]);
    }
  maxp[u]=max(maxp[u],sum-siz[u]);
  if (maxp[rt]>maxp[u])rt=u;
}
ll dep[MaxN],pf[MaxN];
int fa[MaxN],top;
struct Line
{
  ll k,b; double t;
  ll get(ll x){return k*x+b;}
}q[MaxN];
double inter(const Line &A,const Line &B)
{return 1.00*(B.b-A.b)/(A.k-B.k);}
struct Data
{int p;long long lim;}t[MaxN];
int tot; ll lim[MaxN],udep;
void dfs(int u,int fa)
{
  if (lim[u]+udep>=dep[u])
    t[++tot]=(Data){u,lim[u]-dep[u]+udep};
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=fa&&!vis[v])
      dfs(v,u);
}
bool cmp(const Data &A,const Data &B)
{return A.lim<B.lim;}
ll p[MaxN],c[MaxN],F[MaxN];
void calc(int u,int bar)
{
  tot=0;udep=dep[u];
  for (int i=0,v;i<g[u].size();i++)
    if (!vis[v=g[u][i]])
      dfs(v,u);
  sort(t+1,t+tot+1,cmp);

  int tp=fa[u];long long dis=pf[u];
  while (dis<=lim[u]&&tp!=bar){
    F[u]=min(F[u],F[tp]+p[u]*dis+c[u]);
    dis+=pf[tp];tp=fa[tp];
  }
  tp=u;dis=0;top=0;
  for (int i=1;i<=tot;i++){
    while (dis<=t[i].lim&&tp!=bar){
      Line sav=(Line){-dep[tp],F[tp]};
      while(top>1&&q[top].t<eps+inter(q[top-1],sav))
        top--;
      q[++top]=sav;
      if (top>1)
        q[top].t=inter(q[top-1],q[top]);
      else q[top].t=1e18;
      dis+=pf[tp];tp=fa[tp];
    }
    if (top){
      int v=t[i].p,l=1,r=top,mid;
      while(l<r){
        mid=(l+r+1)>>1;
        if (q[mid].t+eps>p[v])l=mid;
        else r=mid-1;
      }
      F[v]=min(F[v],
        q[l].get(p[v])+c[v]+p[v]*dep[v]
      );
    }
  }
}
void solve(int u)
{
  int bar=u;
  while(!vis[bar])bar=fa[bar];
  vis[u]=1;
  if (!vis[fa[u]]){
    rt=0;sum=0;cnt(fa[u],0);
    getrt(fa[u],0);
    solve(rt);
  }calc(u,bar);
  for (int i=0,v;i<g[u].size();i++)
    if (!vis[v=g[u][i]]){
      rt=0;sum=0;cnt(v,0);
      getrt(v,0);
      solve(rt);
    }
}
int n,_t;
int main()
{
  scanf("%d%d",&n,&_t);
  for (int i=2;i<=n;i++){
    fa[i]=read();
    g[fa[i]].push_back(i);
    g[i].push_back(fa[i]);
    dep[i]=dep[fa[i]]+(pf[i]=read());
    p[i]=read();c[i]=read();
    lim[i]=read();
    F[i]=1ll<<60;
  }
  maxp[0]=sum=n;getrt(1,0);
  F[1]=0;vis[0]=1;solve(rt);
  for (int i=2;i<=n;i++)
    printf("%lld\n",F[i]);
  return 0;
}