自动搬运

查看原文

来自洛谷，原作者为

	xtzqhy 2023.7-2024.11||AFO

搬运于2025-08-24 22:59:33，当前版本为作者最后更新于2024-07-16 09:16:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

双倍经验：P2305 [NOI2014] 购票

题解里竟然没有出栈序写法，我来写一篇。

首先列出朴素的 DP 式：

拆开以后发现是个一次函数，直接李超树维护。

但是是链查，难道要树剖加树套树？3 个 $\log$ 难以接受。

这里介绍一个 trick：出栈序，就是每个节点 $\operatorname{dfs}$ 时出栈的时间戳。设时间戳为 $T_i$，如果 $u$ 能直接到 $v$，那么直接查 $[T_u,T_v]$ 就是对的，因为区间内不在路径上的点一定还没被更新到。

原题题解区没有对此给出说明，只是说画图可知。个人感性理解了一下，大概是因为按原顺序 $\operatorname{dfs}$，那么当前在的点一定是所有还没有更新的点中出栈序最小的，那么区间内不在路径上的点一定还没被更新到，所以直接查是正确的。

注意这道题要离散化横坐标（本人因为离散化写错调了半天）。

Code

#include"bits/stdc++.h"
#define re register
#define int long long
#define k(i) (-t[(i)].dis)
#define b(i) (f[(i)])
using namespace std;
const int maxn=1e6+10,inf=1e18;
int n,len,cnt,tim,tot,segcnt;
int v[maxn],w[maxn],head[maxn],f[maxn],c[maxn];
struct edge{
	int to,nxt,w;
}e[maxn<<1];
struct node{
	int dis,out;
}t[maxn];
struct lct{
	int ls,rs,id;
}tr[maxn<<1];
struct line{
	int k,b;
}lin[maxn];
struct tree{
	int rt;
}root[maxn<<2];
inline void add(int u,int v,int w){
	++cnt;
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
inline int calc(int x,int id){return lin[id].k*c[x]+lin[id].b;}
inline void dfs1(int u,int fa){
	for(re int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		t[v].dis=t[u].dis+e[i].w;
		dfs1(v,u);
	}
	t[u].out=++tim;
}
inline void add(int x){
	++tot;
	lin[tot].k=k(x);
	lin[tot].b=b(x);
}
inline void update(int l,int r,int id,int &p){
	if(!p) p=++segcnt;
	int mid=(l+r)>>1;
	if(calc(mid,id)<calc(mid,tr[p].id)) swap(id,tr[p].id);
	if(calc(l,id)<calc(l,tr[p].id)) update(l,mid,id,tr[p].ls);
	if(calc(r,id)<calc(r,tr[p].id)) update(mid+1,r,id,tr[p].rs);
}
inline void update(int l,int r,int pos,int id,int p){
	update(1,len,id,root[p].rt);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(pos<=mid) update(l,mid,pos,id,p<<1);
	else update(mid+1,r,pos,id,p<<1|1);
}
inline int query(int l,int r,int pos,int p){
	if(!p) return inf;
	int mid=(l+r)>>1;
	int res=calc(pos,tr[p].id);
	if(l==r) return res;
	if(pos<=mid) return min(res,query(l,mid,pos,tr[p].ls));
	else return min(res,query(mid+1,r,pos,tr[p].rs));
}
inline int query(int l,int r,int L,int R,int p,int pos){
	if(l>=L&&r<=R) return query(1,len,pos,root[p].rt);
	int mid=(l+r)>>1,res=inf;
	if(L<=mid) res=min(res,query(l,mid,L,R,p<<1,pos));
	if(R>mid) res=min(res,query(mid+1,r,L,R,p<<1|1,pos));
	return res;
}
inline void dfs(int u,int fa){
	if(u!=1) f[u]=query(1,n,t[u].out,t[1].out,1,v[u])+t[u].dis*c[v[u]]+w[u];
	add(u);
	update(1,n,t[u].out,tot,1);
	for(re int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(re int i=1,u,v,w;i<n;++i) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	for(re int i=2;i<=n;++i) cin>>w[i]>>v[i];
	for(re int i=0;i<=n;++i) lin[i].b=inf;
	for(re int i=1;i<n;++i) c[i]=v[i+1];
	sort(c+1,c+n-1+1);
	len=unique(c+1,c+n-1+1)-(c+1);
	for(re int i=2;i<=n;++i) v[i]=lower_bound(c+1,c+len+1,v[i])-c;
	dfs1(1,0);
	dfs(1,0);
	for(re int i=2;i<=n;++i) cout<<f[i]<<" ";
	return 0;
}