UOJ #7 【NOI2014】购票

题目链接：购票

　　这道题我调了好久啊……主要还是因为这种用\(CDQ\)分治来搞斜率优化的题已经很久没写过了……上一次要追溯到去年暑假去了……

　　看下面这些东西之前你需要先自己推出斜率优化的式子……

　　这道题我们先来考虑一下如果不是树，在序列上怎么做。用\(CDQ\)分治的思想，先递归处理左半区间，然后用左半区间的值来更新右半区间，最后递归处理右半区间。这样的话，每次递归处理到一个区间，我们只需要考虑这个区间左边的点对右边的点的影响，对左边的点维护一个凸包，每次在凸包上二分最优解即可。

　　考虑如何把这个拓展到树上。我们树分治的时候每次是找了一个重心出来，然后递归处理剩下的部分。因此，我们在做这道题的时候，只需先递归处理剩下的子树中重心父亲所在的块，然后更新其他点的答案，最后递归其他联通块即可。注意重心需要单独考虑一下。

　　还有一个细节：先把所有祖先拿出来构凸包，然后每次在上面二分是不对的。因为这样可能会出现这种情况：对于一个点\(x\)，它的最优决策是\(u\)，在\(fa_u\)加入了凸包后点\(u\)会被从凸包中踢掉。但是如果\(x\)只能到\(u\)而到不了\(fa_u\)，就挂掉了……因为这里我调了好久……所以我们需要把点抠出来按能够到达的最小深度排序，然后把祖先一个一个往凸包里面加……

　　不知道为什么我的程序好慢……

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 200010

#define INF (1ll<<60)

using namespace std;

typedef long long llg;

int n,fa[maxn],p[maxn],T;

int head[maxn],next[maxn<<1],to[maxn<<1],tt;

llg d[maxn],f[maxn],q[maxn],L[maxn];

struct point{

	llg x,y;

	bool operator < (const point &h)const{return x>h.x;}

	point(llg a=0,llg b=0):x(a),y(b){}

}s[maxn];

struct Convex{//维护下凸包

	point s[maxn];int ls;

	double R(point a,point b){return (double)(b.y-a.y)/(b.x-a.x);}

	void push(point x){

		while(ls>1 && R(s[ls-1],s[ls])<=R(s[ls],x)) ls--;

		s[++ls]=x;

	}

	llg find(int x){//二分斜率

		if(!ls) return INF;

		int l=1,r=ls,mid;

		while(l<r){

			mid=(l+r)>>1;

			if(R(s[mid],s[mid+1])<x) r=mid;

			else l=mid+1;

		}

		return s[l].y-1ll*x*s[l].x;

	}

}tu;

void link(int x,int y){

	to[++tt]=y;next[tt]=head[x];head[x]=tt;

	to[++tt]=x;next[tt]=head[y];head[y]=tt;

}

int a[maxn],la,val[maxn],siz[maxn],dax[maxn];

bool vis[maxn];

void dfs(int u){

	vis[u]=1; a[++la]=u; siz[u]=1; dax[u]=0;

	for(int i=head[u],v;v=to[i],i;i=next[i])

		if(!vis[v]) dfs(v),siz[u]+=siz[v],dax[u]=max(dax[u],siz[v]);

	vis[u]=0;

}

void solve(int ff,int fr){

	la=0; dfs(ff); int k=a[1],ls=0;

	for(int i=1,u;u=a[i],i<=la;i++){

		val[u]=max(dax[u],siz[ff]-siz[u]);

		if(val[u]<val[k]) k=u;

	}

	vis[k]=1; if(!vis[fa[k]]) solve(fa[k],fr);//先处理父亲

	a[la=1]=k;

	for(int i=head[k],v;v=to[i],i;i=next[i])

		if(!vis[v] && v!=fa[k]) dfs(v);

	for(int i=1,u;u=a[i],i<=la;i++) s[i]=point(d[u]-L[u],u);

	ls=la; sort(s+1,s+ls+1); la=0;//把所有需要被更新的点抠出来排序

	for(int u=fa[k];!vis[u];u=fa[u]) a[++la]=u;

	if(fr) a[++la]=fr; tu.ls=0;//上一层的重心没有在上一层考虑，这一层要加进来

	for(int i=1,j=1,u;u=s[i].y,i<=ls;i++){//更新

		while(j<=la && d[a[j]]>=s[i].x) tu.push(point(d[a[j]],f[a[j]])),j++;

		f[u]=min(f[u],tu.find(p[u])+1ll*p[u]*d[u]+q[u]);

	}

	for(int i=head[k],v;v=to[i],i;i=next[i])

		if(!vis[v] && v!=fa[k]) solve(v,k);

	vis[k]=0;

}

int main(){

	File("a");

	scanf("%d %d",&n,&T);

	for(int i=2;i<=n;i++){

		scanf("%d %lld",&fa[i],&d[i]);

		scanf("%d %lld %lld",&p[i],&q[i],&L[i]);

		d[i]+=d[fa[i]]; link(i,fa[i]); f[i]=INF;

	}

	vis[0]=1; solve(1,0);

	for(int i=2;i<=n;i++) printf("%lld\n",f[i]);

	return 0;

}

　　BZOJ提交链接：BZOJ 3672 购票

巴特西

UOJ #7 【NOI2014】购票

最新文章

热门文章

巴特西

UOJ #7 【NOI2014】 购票

最新文章

热门文章

UOJ #7 【NOI2014】购票