专栏文章

P2305 [NOI2014] 购票 题解

lliuziqin
P2305题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min66pbv
此快照首次捕获于
2025/12/01 21:13
3 个月前
此快照最后确认于
2025/12/01 21:13
3 个月前
查看原文
提供一种题解区中没有的做法。
首先式子非常简单
fu=min⁡v∈fau,du−dv≤lufv+(du−dv)pu+qu=−pudv+fv+dupu+quf_{u}=\min_{v \in fa_u,d_u-d_v \le l_u} f_v+(d_u-d_v)p_u+q_u \\=-p_ud_v+f_v+d_up_u+q_u
在链上且没有 lul_u 的限制就是李超线段树的板子题。
如果说放在树上，不考虑 lul_u 的限制，我们可以用可撤销李超维护，在离开节点 uu 时撤销在该点的线段即可。
现在加上 lul_u 的限制，结合之前的算法，考虑线段树套可撤销李超线段树。
我们每次在外层线段树 depudep_u 的位置插入一条线段，在 log⁡n\log n 棵李超线段树上进行修改，查询时找出合法的深度区间，最后在退出 dfs 时进行撤销操作即可。
卡常小技巧
  1. 把线段放李超外面存储，可以节省不少空间。
  2. 把 stack 改为手写邻接表，减少 STL 空间常数。
  3. 最后一次退出循环时不进行撤销操作。
  4. 快读快写。
C
#include<bits/stdc++.h>
#define ll long long
#define il inline 
#define re register
using namespace std;
inline char gc(){
    static char buf[1<<20],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<< 20,stdin),p1==p2)?EOF:*p1++;
}
inline void read(ll &n){
    bool w=0;
    char c=gc();
    for(;c<48||c>57;c=gc())
        w=c==45;
    for(n=0;c>=48&&c<=57;c=gc())
        n=n*10+c-48;
    n=w?-n:n;
}
char buf[1<<21];
int p1=-1;
const int p2=(1<<21)-1;
inline void flush(){fwrite(buf,1,p1+1,stdout); p1=-1;}
inline void pc(const char &x){if(p1==p2) flush(); buf[++ p1]=x;}
inline void write(ll x,char a){
    if(x<0)pc(45),x=-x;
    char c[21],s=0;
    for(;x;)c[s++]=x%10,x/=10;
    if(!s)pc(48);
    for(;s--;)pc(c[s]+48);
    pc(a);
}
const int N=200005;
const ll INF=1e18;
const int nn=1000000;
struct edge{
	int to,nxt;
	ll w;
}e[N<<1];
int head[N],cur;
il void add_edge(int u,int v,ll w){
	e[++cur].to=v;
	e[cur].nxt=head[u];
	e[cur].w=w;
	head[u]=cur;
}
struct line{
	ll k,b;
	int id;
	il ll calc(ll x){
		return k*x+b;
	}
};
il bool operator ==(line a,line b){
	return a.k==b.k&&a.b==b.b&&a.id==b.id;
}
line sum[N];
struct segtree{
	int ls[N*100],rs[N*100],cnt;
	int top1[N*100],nxt1[N*100],id1[N*100],tot1;
	int top2[N*100],nxt2[N*100],id2[N*100],tot2;
	il void update(int &p,int l,int r,int x){
		if(!p){
			p=++cnt;
			id1[++tot1]=x;
			top1[p]=tot1;
			return ;
		}
		int ud=id1[top1[p]];
		if(!top1[p]||sum[x].calc(l)<=sum[ud].calc(l)&&sum[x].calc(r)<=sum[ud].calc(r)){
			id1[++tot1]=x;
			nxt1[tot1]=top1[p];
			top1[p]=tot1;
			return ;
		}
		if(top1[p]&&sum[x].calc(l)>=sum[ud].calc(l)&&sum[x].calc(r)>=sum[ud].calc(r)){
			id2[++tot2]=x;
			nxt2[tot2]=top2[p];
			top2[p]=tot2;
			return ;
		}
		int mid=(l+r)>>1;
		update(ls[p],l,mid,x);
		update(rs[p],mid+1,r,x);
	}
	il ll query(int p,int l,int r,int x){
		if(!p)return INF;
		int ud=id1[top1[p]];
		ll ans=sum[ud].calc(x);
		if(!top1[p])ans=INF;
		if(l==r)return ans;
		int mid=(l+r)>>1;
		if(mid>=x)return min(ans,query(ls[p],l,mid,x));
		else return min(ans,query(rs[p],mid+1,r,x));
	}
	il void del(int p,int l,int r,int x){
		if(!p)return ;
		if(top1[p]&&id1[top1[p]]==x){
			top1[p]=nxt1[top1[p]];
			return ;
		}
		if(top2[p]&&id2[top2[p]]==x){
			top2[p]=nxt2[top2[p]];
			return ;
		}
		int mid=(l+r)>>1;
		del(ls[p],l,mid,x);
		del(rs[p],mid+1,r,x);
	}
}st;
struct segtree_to_segtree{
	int rt[N<<2];
	il void update(int p,int l,int r,int x,int v){
		st.update(rt[p],0,nn,v);
		if(l==r)return ;
		int mid=(l+r)>>1;
		if(mid>=x)update(p*2,l,mid,x,v);
		else update(p*2+1,mid+1,r,x,v);
	}
	il void del(int p,int l,int r,int x,int v){
		st.del(rt[p],0,nn,v);
		if(l==r)return ;
		int mid=(l+r)>>1;
		if(mid>=x)del(p*2,l,mid,x,v);
		else del(p*2+1,mid+1,r,x,v);
	}
	il ll query(int p,int l,int r,int x,int y,int tx){
		if(l>=x&&r<=y)return st.query(rt[p],0,nn,tx);
		int mid=(l+r)>>1;
		ll ans=INF;
		if(mid>=x)ans=min(ans,query(p*2,l,mid,x,y,tx));
		if(mid<y)ans=min(ans,query(p*2+1,mid+1,r,x,y,tx));
		return ans;
	}
}st2;
ll p[N],q[N],l[N],n,dis[N],dp[N],crr;
int dep[N],fa[N][25],last[N],mx;
il void dfs0(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	last[u]=u;
	mx=max(mx,dep[u]);
	for(re int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(re int i=20;i>=0;i--)
		if(dis[u]-dis[fa[last[u]][i]]<=l[u]&&fa[last[u]][i])last[u]=fa[last[u]][i];
	for(re int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;
		if(v==f)continue;
		dis[v]=dis[u]+w;
		dfs0(v,u);
	}
}
il void dfs1(int u,int fa){
	crr++;
	if(u==1){
		dp[u]=0;
		sum[u]={0,0,1};
		st2.update(1,1,mx,1,1);
	}
	else{
		dp[u]=st2.query(1,1,mx,dep[last[u]],dep[u],p[u])+dis[u]*p[u]+q[u];
		sum[u]={-dis[u],dp[u],u};
		st2.update(1,1,mx,dep[u],u);
	}
	for(re int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dfs1(v,u);
	}
	if(crr<n)st2.del(1,1,mx,dep[u],u);
}
signed main(){
	ll _;
	read(n),read(_);
	for(int i=2;i<=n;i++){
		ll v,w;
		read(v),read(w),read(p[i]),read(q[i]),read(l[i]);
		add_edge(v,i,w);
		add_edge(i,v,w);
	}
	dfs0(1,0);
	dfs1(1,0);
	for(re int i=2;i<=n;i++)write(dp[i],'\n');
	flush();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...