【NOI2014】购票
因为太麻烦了，而且暴露了我很多学习不扎实的问题，所以记录一下具体做法。
主要算法:点分治+凸包优化斜率DP。
因为$q_i$不单调，所以需要在凸包上二分求最优解。
因为有$L_i$的限制，并且删除凸包左边的点会导致一些问题，所以就改变枚举顺序（倒着加入祖先链），使问题变成不用删点。因此直接套用凸包二分求解的模板。
大致流程：
Tree_Divide_conquer(fa[x]).//先求出祖先链的Dp值
Get_all_son();//将除了x父亲那一端，该重心层的点都放A中
sort(A+,A++now);//按dis_i-L_i递减排序
for(int i=,t=fa[x];i<=now;i++)
{
for(;t!=fa[up]&&dis[t]>=dis[A[i]]-l[A[i]];t=fa[t])//up记录该重心层深度最浅的点的父亲
ADD(t);
UPD(A[i]);//在凸包上二分
}
Tree_Divide_conquer(....)//分治其他子树
Code:
#include<cstdio>
#include<algorithm> typedef long long ll;
template<class T>
inline void read(T&x)
{
x=;bool f=;char c=getchar();
while((c<''||c>'')&&c!='-')c=getchar(); if(c=='-')f=,c=getchar();
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
x=f?-x:x;
}
const int MAXN();
const ll INF(0x7fffffffffffffff);
struct Node{int nd,nx;}bot[MAXN<<];int tot,first[MAXN];
void add(int a,int b){bot[++tot]=(Node){b,first[a]},first[a]=tot;}
int n,t,fa[MAXN],p[MAXN];ll f[MAXN],l[MAXN],dis[MAXN],s[MAXN],q[MAXN],last[MAXN];
//===================================var
int st[MAXN],tp;
ll sum(int x,int y)
{
return f[y]+(dis[x]-dis[y])*(ll)p[x]+q[x];
}
double slope(int u,int v)
{
return 1.0*(f[u]-f[v])/(dis[u]-dis[v]);
}
void UPD(int x)
{
int li=,ri=tp-,mid,Ans=tp;
for(;li<=ri;)
{
mid=(li+ri)>>;
if(slope(st[mid+],st[mid])<=p[x])ri=mid-,Ans=mid;else li=mid+;
}
if(Ans<=tp&&tp)
{
ll tmp=sum(x,st[Ans]);
if(f[x]>=tmp)f[x]=tmp,last[x]=st[Ans];
}
}
void ADD(int x)
{
while(tp>&&slope(st[tp-],st[tp])<slope(st[tp],x))
tp--;
st[++tp]=x;
}
//===================================斜率优化/凸包
int size[MAXN],big[MAXN],col[MAXN],root[MAXN],flag[MAXN],all;
void Get_size(int x,int f)
{
size[x]=;big[x]=;
for(int v=first[x];v;v=bot[v].nx)
if(bot[v].nd!=f&&flag[bot[v].nd]==)
{
Get_size(bot[v].nd,x);
size[x]+=size[bot[v].nd];
big[x]=std::max(big[x],size[bot[v].nd]);
}
}
void Get_root(int x,int f)
{
col[x]=col[f];
for(int v=first[x];v;v=bot[v].nx)
if(bot[v].nd!=f&&flag[bot[v].nd]==)
Get_root(bot[v].nd,x);
big[x]=std::max(big[x],all-size[x]);
if(big[x]*<=all)root[col[x]]=x;
}
int A[MAXN],now;
bool cmp(int a,int b){return dis[a]-l[a]>dis[b]-l[b];}
void Get_ans(int x,int f)
{
for(int v=first[x];v;v=bot[v].nx)
if(bot[v].nd!=f&&flag[bot[v].nd]==)
Get_ans(bot[v].nd,x);
A[++now]=x;
}
void Tree_Dive_And_Conquer(int x)
{
int up=x;while(!flag[up])up=fa[up];
flag[x]=;
for(int v=first[x];v;v=bot[v].nx)
if(!flag[bot[v].nd])
{
col[x]=bot[v].nd;
Get_size(bot[v].nd,x);all=size[bot[v].nd];
Get_root(bot[v].nd,x);
}
if(!flag[fa[x]])Tree_Dive_And_Conquer(root[fa[x]]);
A[now=]=x;
for(int v=first[x];v;v=bot[v].nx)
if(!flag[bot[v].nd])Get_ans(bot[v].nd,x);
std::sort(A+,A++now,cmp);
tp=;
for(int i=,t=fa[x];i<=now;i++)
{
for(;t!=fa[up]&&dis[t]>=dis[A[i]]-l[A[i]];t=fa[t])
ADD(t);
UPD(A[i]);
}
for(int v=first[x];v;v=bot[v].nx)
if(!flag[bot[v].nd])Tree_Dive_And_Conquer(root[bot[v].nd]);
}//O(nlog^2n)
void run()
{
Get_size(,);
for(int i=;i<=n;i++)
{
big[i]=std::max(big[i],n-size[i]);
if(big[i]*<=n)root[]=i;
}
flag[]=;Tree_Dive_And_Conquer(root[]);
}
//===================================点分治
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
read(n);read(t);
for(int i=;i<=n;i++)
{
read(fa[i]);read(s[i]);read(p[i]);read(q[i]);read(l[i]);
add(i,fa[i]);add(fa[i],i);dis[i]=dis[fa[i]]+s[i];f[i]=INF;
}
run();
for(int i=;i<=n;i++)printf("%lld\n",f[i]);
return ;
}