自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 21:36:10，当前版本为作者最后更新于2020-10-09 09:40:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

新做法：线段树套李超树+出栈序。

$O(n^2)$ 的 dp 方程：$f_i=\min(f_j+(d_i-d_j)p_i+q_i)$，其中 $j$ 为 $i$ 的祖先，且 $d_i-d_j\leq l_i$。初始值 $f_1=0$。

式子拆开：$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)$。

#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;
}