题解 P2305 【[NOI2014]购票】
panyf
·
·
题解
新做法：线段树套李超树+出栈序。
式子拆开：$f_i=d_ip_i+q_i+\min(-d_jp_i+f_j)$。
设 $y=f_i-d_ip_i-q_i$，$k=-d_j$，$x=p_i$，$b=f_j$，则有 $y=\min(kx+b)$。
数据类型 $t=0$ 时，显然是李超树模板题。
$t=1$ 时，边 dfs 边处理，当离开一个结点时需要撤销对应的直线。和维护凸壳相比，李超树的优势在于方便撤销（可持久化或者用栈记录修改操作）。时空复杂度均为 $O(n\log n)$。
$t=2$ 时，有了 $l$ 的限制，需要支持区间查询，考虑树套树，每次在 $\log n$ 棵李超树上修改和查询。时间复杂度 $O(n\log^2n)$，空间 $O(n\log n)$。
为什么空间复杂度不是 $O(n\log^2n)$？李超树与一般的线段树不同，信息可以在非叶子结点保存，因此动态开点的李超树空间复杂度可以做到 $O(n)$。具体方法是每次插入直线时遇到空结点就 return，这样每次只会新建一个结点。总的空间复杂度即为 $O(n\log n)$。
$t=3$ 时，直接结合 $t=1$ 和 $2$ 的做法，线段树套可撤销李超树，时空复杂度均为 $O(n\log^2n)$，卡空间后可以通过。
有没有不需要卡空间的做法？空间瓶颈是李超树的撤销。注意到要做的操作是树链查询最小值， 可以树链剖分套线段树套李超树，就不需要撤销了，空间复杂度 $O(\log n)$，时间复杂度 $O(n\log^3n)$，但常数很小，可以通过（尝试构造了卡树剖的数据效果并不理想，而且这个做法在 uoj 也可以通过）。
更好的做法是利用**出栈序**，也就是每个结点离开 dfs 的顺序。直接在点 $i$ 及其最远的满足 $d_i-d_j\leq l_i$ 的祖先 $j$ 的出栈序对应的区间上查询。容易发现区间内不在 $i$ 和 $j$ 的路径上的点都未被访问到，不会对答案产生贡献。这样就不需要树链剖分了。时间复杂度 $O(n\log^2n)$，空间复杂度 $O(n\log n)$。
upd：李超树的优势在于方便撤销~~以及码量小~~，而最终的做法并没有用到撤销。因此其他题解的树剖+线段树+凸壳上二分的做法也可以用类似的方式优化到 $O(n\log^2n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+3,M=4e6+3;
int rt[N*3],n,he[N],ne[N],p[N],o[N],t[M],lc[M],rc[M],c[N],id,u,v,w,m;
ll s[N],q[N],l[N],d[N],f[N],a[N],b[N];
#define g(t,x) (a[t]*(x)+b[t])
void tupd(int&k,int l,int r){//李超树插入直线（动态开点）
if(k){
int m=l+r>>1;
if(g(w,m)<g(t[k],m))swap(w,t[k]);
if(l<r)a[w]<a[t[k]]?tupd(rc[k],m+1,r):tupd(lc[k],l,m);
}else t[k=++id]=w;
}
ll tqry(int k,int l,int r){//李超树查询最小值
if(!k)return 1e18;
int m=l+r>>1;
return min(g(t[k],w),w>m?tqry(rc[k],m+1,r):tqry(lc[k],l,m));
}
void upd(int k,int l,int r){//外层线段树单点修改
w=v,tupd(rt[k],0,1e6);
if(l==r)return;
int m=l+r>>1;
u>m?upd(k*2+1,m+1,r):upd(k*2,l,m);
}
ll qry(int k,int l,int r){//外层线段树区间查询
if(u<=l&&r<=v)return tqry(rt[k],0,1e6);
int m=l+r>>1;
return u>m?qry(k*2+1,m+1,r):(m<v?min(qry(k*2,l,m),qry(k*2+1,m+1,r)):qry(k*2,l,m));
}
void pre(int x){//预处理出栈序
for(int i=he[x];i;i=ne[i])pre(i);
o[x]=++id;
}
void dfs(int x){
a[x]=-d[m],b[x]=f[x],u=o[v=c[m]=x],upd(1,1,n);
for(int i=he[x];i;i=ne[i]){
++m,d[m]=d[m-1]+s[i],u=o[i],v=o[c[lower_bound(d,d+m,d[m]-l[i])-d]];
w=p[i],f[i]=qry(1,1,n)+d[m]*w+q[i],dfs(i),--m;
}
}
int main(){
int i,j;
scanf("%d%*d",&n);
for(i=2;i<=n;++i)scanf("%d%lld%d%lld%lld",&j,s+i,p+i,q+i,l+i),ne[i]=he[j],he[j]=i;
pre(1),id=0,dfs(1);
for(i=2;i<=n;++i)printf("%lld\n",f[i]);
return 0;
}
```