【JZOJ5081】【GDSOI2017第三轮模拟】Travel Plan 背包问题+双指针+树的dfs序

题面

100

注意到ban的只会是一个子树，所以我们把原树转化为dfs序列。

然后题目就转化为，询问一段ban的区间，之后的背包问题。

比赛的时候，我想到这里，于是就开始想区间合并，于是搞了线段树合并，遂无果，爆零。

由于ban的是一段区间，所以肯定是将前缀和后缀合并。

我们预处理出前缀背包，和后缀背包。

然后合并两个背包就可以了。

具体的合并，Two pointers。

还要卡常。

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

#define ui unsigned int

#define fo(i,x,y) for(int i=x;i<=y;i++)

#define fd(i,x,y) for(int i=x;i>=y;i--)

using namespace std;

const char* fin="plan.in";

const char* fout="plan.out";

const int maxn=1007,maxm=maxn*2,maxv=50007,maxt=2000;

int n,m,fi[maxn],la[maxm],ne[maxm],tot,mx,pre[maxn],suf[maxn],A,B;

int dfn[maxn],low[maxn],num,va[maxn],co[maxn],a[maxv],b[maxv];

ui f[maxn][maxv],g[maxn][maxv],inf;

void add_line(int a,int b){

	tot++;

	ne[tot]=fi[a];

	la[tot]=b;

	fi[a]=tot;

}

void dfs(int v,int from){

	dfn[v]=++num;

	for(int k=fi[v];k;k=ne[k])

		if (la[k]!=from)

			dfs(la[k],v);

	low[v]=num;

}

void dp(ui *f,ui *g,int v){

	fd(i,mx,0){

		if (g[i]==inf) continue;

		f[i+va[v]]=(f[i+va[v]]<g[i]+co[v]?f[i+va[v]]:g[i]+co[v]);

		f[i]=(f[i]<g[i]?f[i]:g[i]);

		mx=(mx>i+va[v]?mx:i+va[v]);

	}

	fd(i,mx-1,0) f[i]=(f[i+1]<f[i]?f[i+1]:f[i]);

}

int main(){

	freopen(fin,"r",stdin);

	freopen(fout,"w",stdout);

	scanf("%d",&n);

	fo(i,1,n-1){

		int j,k;

		scanf("%d%d",&j,&k);

		add_line(j,k);

		add_line(k,j);

	}

	dfs(1,0);

	fo(i,1,n) scanf("%d%d",&va[dfn[i]],&co[dfn[i]]);

	inf=-1;

	memset(f,255,sizeof f);

	memset(g,255,sizeof g);

	f[0][0]=0;

	g[n+1][0]=0;

	mx=pre[0]=0;

	fo(i,1,n) dp(f[i],f[i-1],i),pre[i]=mx;

	mx=suf[n+1]=0;

	fd(i,n,1) dp(g[i],g[i+1],i),suf[i]=mx;

	scanf("%d",&m);

	fo(i,1,m){

		int x;

		ui lim;

		scanf("%d%ud",&x,&lim);

		A=dfn[x]-1;B=low[x]+1;

		int k=suf[B],ans=0;

		fo(j,0,pre[A]){

			if (f[A][j]==inf) continue;

			while (k>=0 && (g[B][k]==inf || f[A][j]+g[B][k]>lim))

				k--;

			if (k<0) break;

			ans=max(j+k,ans);

		}

		printf("%d\n",ans);

	}

	return 0;

}