• 欢迎光临~

P2305 [NOI2014] 购票

开发技术 开发技术 2022-10-06 次浏览

P2305 [NOI2014] 购票

(f_{x}) 表示从 (x) 点跳到 (1) 的最少费用。考虑 (x) 的一个祖先 (u),有

[f_x=f_{u}+text{dis}_{u,x}times p_x+q_x ]

其中需要满足 (text{dis}_{u,x}le l_x)

由于 (p)(x) 的祖先,考虑前缀和来化简 (text{dis}_{u,x})。记 (text{pre}_x) 表示根节点 (1)(x) 的简单路径长度。则有 (text{dis}_{u,x}=text{pre}_x-text{pre}_p)。带入原式并化简得到

[f_{x}=f_u+text{pre}_xtimes p_x-text{pre}_utimes p_x+q_x ]

(-text{pre}_u) 看作 (k),容易得到斜率优化的形式。

由于需要满足条件 (text{pre}_x-text{pre}_p le l_x),考虑外层套用线段树,则内层使用李超线段树实现较为简单。

由于需要找到点的祖先节点区间,线段树遍历顺序采用原树的出栈序。

至此,可以得到一个线段树套李超线段树的 (mathcal{O}(n log^2 n)) 的做法,可以通过。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 200005
#define M 1000005 
#define Maxn 1000000
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int n,typ,cnt,head[N],num; 
struct object{
	ll f,s,p,q,l;
}a[N];
struct edge{
	int v,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct line{
	ll k,b;
}L[N];
inline int insert(ll k,ll b){
	L[++num]=(line){k,b};
	return num;
}
inline ll calc(int id,ll x){
	return L[id].k*x+L[id].b;
}
struct LC_Tree{
	struct node{
		int ls,rs,s;
	}t[M*30];
	#define lc(x) t[x].ls
	#define rc(x) t[x].rs
	#define s(x) t[x].s
	int Idx;
	inline void update(int &x,int l,int r,int pos){
		if(!x) return t[x=++Idx].s=pos,void();
		int mid=l+r>>1;
		if(calc(s(x),mid)>calc(pos,mid)) swap(s(x),pos);
		if(calc(s(x),l)>calc(pos,l)) update(lc(x),l,mid,pos);
		if(calc(s(x),r)>calc(pos,r)) update(rc(x),mid+1,r,pos);
	}
	inline ll query(int x,int l,int r,int pos){
		if(!x) return inf;
		ll res=calc(s(x),pos);
		int mid=l+r>>1;
		if(pos<=mid) res=min(res,query(lc(x),l,mid,pos));
		else res=min(res,query(rc(x),mid+1,r,pos));
		return res;
	}
	#undef lc
	#undef rc
	#undef s
}T;
int rt[N<<2];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
inline void update(int x,int l,int r,int pos,int k){
	T.update(rt[x],0,Maxn,k);
	if(l==r) return;
	int mid=l+r>>1;
	if(pos<=mid) update(lc(x),l,mid,pos,k);
	else update(rc(x),mid+1,r,pos,k);
}
inline ll query(int x,int l,int r,int ql,int qr,int k){
	if(ql<=l&&qr>=r) return T.query(rt[x],0,Maxn,k);
	ll res=inf;
	int mid=l+r>>1;
	if(ql<=mid) res=min(res,query(lc(x),l,mid,ql,qr,k));
	if(qr>mid) res=min(res,query(rc(x),mid+1,r,ql,qr,k));
	return res;
}
#undef lc
#undef rc
ll f[N],pre[N];
int id[N],idx,tp,c[N];
inline void prework(int x){
	for(int i=head[x];i;i=e[i].nxt) prework(e[i].v);
	id[x]=++idx;
}
inline void dfs(int x){
	update(1,1,n,id[x],insert(-pre[tp],f[x]));
	c[tp]=x;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		tp++;
		pre[tp]=pre[tp-1]+a[v].s;
		int L=id[v],R=id[c[lower_bound(pre,pre+tp,pre[tp]-a[v].l)-pre]];
		f[v]=query(1,1,n,L,R,a[v].p)+pre[tp]*a[v].p+a[v].q;
		dfs(v),c[tp]=0,tp--;
	}
}
int main(){
	read(n,typ);
	for(int i=2;i<=n;i++)
		read(a[i].f,a[i].s,a[i].p,a[i].q,a[i].l),add(a[i].f,i);
	prework(1),dfs(1);
	for(int i=2;i<=n;i++) put('n',f[i]);
	return 0;
}
程序员灯塔
转载请注明原文链接:P2305 [NOI2014] 购票
喜欢 (0)