http://www.lydsy.com/JudgeOnline/problem.php?id=3672
法一：线段树维护可持久化单调队列维护凸包 斜率优化DP
设dp[i] 表示i号点到根节点的最少花费
dis[i] 表示 点i到根节点的距离
dp[i]= min { （dis[i]-dis[j]）* P[i] + Q[i] + dp[j] } j是i的祖先且dis[i]-dis[j]<=L[i]
即 dp[i]+dis[j]*P[i]=dp[j]+dis[i]*P[i]+Q[i]
斜率优化，dp[i]=斜率为P[i] 的直线 截（dis[j],dp[j]）所得的截距最小值
如果不考虑L[i] 的限制：
那就可以用一个可持久化的单调队列维护 根节点到当前点的路径上所有的点构成的下凸壳
考虑如何去除兄弟节点的子树对单调队列的影响
即在一个节点退出dfs时，将单调队列恢复为这个节点开始dfs的情况
头指针：头指针的前移不会涉及单调队列元素的修改，因为从根往下走不能保证斜率单调，所以头指针不能出队，需要二分找到最小的 斜率>P[i] 的点来更新dp[i]
尾指针：尾指针的前移会涉及到单调队列元素的替换，但替换只会替换一个元素，所以记录下 替换的是谁，原来的尾指针是谁，退出的时候恢复即可
加上L[i]的限制：
用线段树维护，若线段树节点的区间为[l,r]，那这个节点维护的是当前链上 深度为[l,r]的点构成的凸包
即由原来的维护一个单调队列变成维护nlogn个单调队列
每个节点开一个vector？ 光开nlogn个vector就TLE了吧
开一个nlogn的数组v存储整条链上凸包内的点
在建树的时候，按节点的顺序给头指针分一个位置x，若节点的大小为y，
那么这个节点维护的单调队列 中的点会出现在v数组的[x,x+y-1]位置
这样线段树内只需要存储单调队列的头尾指针即可
单调队列采用 左闭右开 的好处：
多个可持久化单调队列，头尾指针相连
如果头尾指针是左闭右闭
如果队列为空，tail<head,导致 后一个队列的尾指针=前一个队列的头指针
这样尾指针替换更改，记录的替换位置为tail，即前一个队列的head
退出dfs替换回去 错误的替换了前一个队列的head
头尾指针左闭右开就不会有这个问题
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 200001 typedef long long LL; int n;
int P[N];
LL Q[N],L[N]; int front[N],to[N],nxt[N],tot;
LL val[N]; struct node
{
int head,tail;
}tr[N<<];
int v[N*]; int sum; LL dep[N],dis[N];
LL dp[N]; int re_t[N][],re_w[N][]; template<typename T>
void read(T &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,LL w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
} void build(int k,int l,int r)
{
tr[k].head=sum+;
tr[k].tail=tr[k].head;
sum+=r-l+;
if(l==r) return;
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
} inline double slope(int i,int j)
{
return 1.0*(dp[j]-dp[i])/(dis[j]-dis[i]);
} int find_ans(int k,int p)
{
int l=tr[k].head;
int r=tr[k].tail-;
if(l==r) return v[l];
r--;
int mid,tmp=-;
while(l<=r)
{
mid=l+r>>;
if(p<slope(v[mid],v[mid+])) tmp=mid,r=mid-;
else l=mid+;
}
if(tmp==-) return v[tr[k].tail-];
return v[tmp];
} int query(int k,int l,int r,int opl,int opr,int p)
{
if(l>=opl && r<=opr) return find_ans(k,p);
int mid=l+r>>;
if(opr<=mid) return query(k<<,l,mid,opl,opr,p);
else if(opl>mid) return query(k<<|,mid+,r,opl,opr,p);
else
{
int t1=query(k<<,l,mid,opl,opr,p);
int t2=query(k<<|,mid+,r,opl,opr,p);
if(p<slope(t1,t2)) return t1;
return t2;
}
} int find(int r,LL lim)
{
int l=;
int tmp,mid;
while(l<=r)
{
mid=l+r>>;
if(dep[mid]>=lim) tmp=mid,r=mid-;
else l=mid+;
}
return tmp;
} int in_queue(int k,int j)
{
if(tr[k].head==tr[k].tail) return tr[k].head;
int l=tr[k].head,r=tr[k].tail-,tmp=-,mid;
while(l<=r)
{
mid=l+r>>;
if(slope(v[mid],v[mid+])>slope(v[mid],j)) tmp=mid+,r=mid-;
else l=mid+;
}
if(tmp==-) return tr[k].tail;
return tmp;
} void insert(int k,int l,int r,int x,int w,int d)
{
int pos=in_queue(k,w);
re_t[w][d]=tr[k].tail;
re_w[w][d]=v[pos];
v[pos]=w;
tr[k].tail=pos+;
if(l==r) return;
int mid=l+r>>;
if(x<=mid) insert(k<<,l,mid,x,w,d+);
else insert(k<<|,mid+,r,x,w,d+);
} void del(int k,int l,int r,int x,int w,int d)
{
v[tr[k].tail-]=re_w[w][d];
tr[k].tail=re_t[w][d];
if(l==r) return;
int mid=l+r>>;
if(x<=mid) del(k<<,l,mid,x,w,d+);
else del(k<<|,mid+,r,x,w,d+);
} void dfs(int x,int d)
{
if(x!=)
{
LL lim=dis[x]-L[x];
int j=query(,,n,find(d-,lim),d-,P[x]);
dp[x]=(dis[x]-dis[j])*P[x]+Q[x]+dp[j];
}
insert(,,n,d,x,);
for(int i=front[x];i;i=nxt[i])
{
dis[to[i]]=dis[x]+val[i];
dep[d+]=dep[d]+val[i];
dfs(to[i],d+);
}
del(,,n,d,x,);
} int main()
{
int t;
read(n); read(t);
int f; LL s;
for(int i=;i<=n;++i)
{
read(f); read(s); read(P[i]); read(Q[i]); read(L[i]);
add(f,i,s);
}
sum=; build(,,n);
insert(,,n,,,);
dfs(,);
for(int i=;i<=n;++i) cout<<dp[i]<<'\n';
return ;
}
法二、点分治+斜率优化dp
朴素的dp是往上找能更新它的点
这里往下找它能更新的点
具体做法：
找出分治重心后，先 解决重心 的祖先（包括重心）那块儿
然后求出 原树根节点到重心的凸包 更新重心的子树
至于 距离的限制，我们把重心的子树中所有点 按能更新它的 深度最小的城市 从大到小排序
枚举这些点i
构造重心到原树根节点的凸包时，从重心往上依次加点，只加入 深度>= 当前点i深度限制 的点
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 200001 typedef long long LL; int n;
int front[N],nxt[N],to[N],tot;
LL val[N]; int fa[N],P[N];
LL Q[N],L[N]; LL dis[N]; bool vis[N]; int root;
int siz[N],mx[N]; struct node
{
int id;
LL lim;
}e[N];
int cnt;
int st[N]; LL dp[N]; template<typename T>
void read(T &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,LL w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
} void dfs(int x)
{
for(int i=front[x];i;i=nxt[i])
{
dis[to[i]]=dis[x]+val[i];
dfs(to[i]);
}
} void get_siz(int x,int all)
{
siz[x]=; mx[x]=;
for(int i=front[x];i;i=nxt[i])
if(!vis[to[i]])
{
get_siz(to[i],all);
siz[x]+=siz[to[i]];
if(siz[to[i]]>mx[x]) mx[x]=siz[to[i]];
}
mx[x]=max(mx[x],all-siz[x]);
if(mx[x]<mx[root] && siz[x]>) root=x;
} void dfs2(int x)
{
e[++cnt].id=x;
e[cnt].lim=dis[x]-L[x];
for(int i=front[x];i;i=nxt[i])
if(!vis[to[i]]) dfs2(to[i]);
} bool cmp(node p,node q)
{
return p.lim>q.lim;
} double slope(int i,int j)
{
return 1.0*(dp[j]-dp[i])/(dis[j]-dis[i]);
} void solve(int x,int all)
{
if(all==) return;
root=;
get_siz(x,all);
int rt=root;
for(int i=front[root];i;i=nxt[i])
vis[to[i]]=true;
solve(x,all-siz[root]+);
cnt=;
for(int i=front[rt];i;i=nxt[i])
dfs2(to[i]);
sort(e+,e+cnt+,cmp);
int now=rt,top=;
for(int i=;i<=cnt;++i)
{
while(now!=fa[x] && e[i].lim<=dis[now])
{
while(top> && slope(st[top],st[top-])<slope(now,st[top])) top--;
st[++top]=now;
now=fa[now];
}
if(top)
{
int l=,r=top-,mid,tmp=-;
while(l<=r)
{
mid=l+r>>;
if(slope(st[mid],st[mid+])>=P[e[i].id]) tmp=mid+,l=mid+;
else r=mid-;
}
if(tmp==-) tmp=;
dp[e[i].id]=min(dp[e[i].id],(dis[e[i].id]-dis[st[tmp]])*P[e[i].id]+Q[e[i].id]+dp[st[tmp]]);
}
}
for(int i=front[rt];i;i=nxt[i])
solve(to[i],siz[to[i]]);
} int main()
{
int t;
read(n); read(t);
LL s;
for(int i=;i<=n;++i)
{
read(fa[i]); read(s); read(P[i]); read(Q[i]); read(L[i]);
add(fa[i],i,s);
}
dfs();
mx[]=n+;
for(int i=;i<=n;++i) dp[i]=2e17+1e12;
solve(,n);
for(int i=;i<=n;++i) cout<<dp[i]<<'\n';
}
3672: [Noi2014]购票
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 1520 Solved: 768
[Submit][Status][Discuss]
Description
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
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
150
70
149
300
150