luogu P5558 心上秋

唐多令宋吴文英

何处合成愁。离人心上秋。纵芭蕉，不雨也飕飕。都道晚凉天气好，有明月，怕登楼。

年事梦中休。花空烟水流。燕辞归，客尚淹留。垂柳不萦裙带住。漫长是，系行舟。

心上秋笔下梅笙中月。

此题求树上任意两点之间的最长不下降子序列权值集合为{1~5}.

\(n<=30000,m<=300000\)

考虑暴力把链抽出来然后暴力dp.最长不下降子序列的dp是nlogn的所以总复杂度为nlognm.

优化暴力发现权值集合很小把链抽出来之后设f[i][j]表示到达第i个点权值为j的最长长度多了一个五倍的常数不过复杂度O(n) 总复杂度nm.

考虑优化如果权值集合只有1,2怎么办？

不妨考虑倍增设f[i][j][k][w]表示从i跳到2^j的祖先经过的边的权值从k到w的最长不降子序列的长度。

发现这个东西可以合并.

对于所有数据我们可以倍增预处理出这个数组。

对于某个询问(x,y) 我们先让x调到lca累计一个数组g[k]表示小于等于k的路径的最长长度然后再从lca跳到y即可。

跟保卫王国的倍增dp有点像不过我没写过那道题的倍增dp 回来可以看一下值得一提的是这道题没有修改所以就简单了很多。

我觉得树剖不太能写的样子矩阵不是很好维护.

我写的有点繁琐了。大体上有一个坑点：注意g数组的维护要维护某个区间的答案初始化和转移要注意。

在最后求答案的时候也注意由lca跳向y的时候要反着做. 数组下标也得反着.所以g数组也要有一个反着的值.

通过这道题我们发现可以扩展到序列上如求某段序列的最长不下降子序列也可以使用这种倍增的方法来做。

可见倍增是优化dp的一种常用手段。

const int MAXN=30010;

int n,m,len,maxx,ans;

int ql[MAXN],qr[MAXN],wl[MAXN],wr[MAXN],top1,top2;

int g[MAXN][16][6][6],f[MAXN][16],Log[MAXN],d[MAXN],w[MAXN][6];

int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],e[MAXN<<1];

inline void add(int x,int y,int z)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

	e[len]=z;

}

inline void dfs(int x,int father)

{

	d[x]=d[father]+1;

	f[x][0]=father;

	rep(1,Log[d[x]],i)

	{

		f[x][i]=f[f[x][i-1]][i-1];

		rep(1,maxx,k)

			rep(1,maxx,w)

			{

				int s1=min(k,w),s2=max(k,w);

				rep(s1,s2,l)g[x][i][k][w]=max(g[x][i][k][w],g[x][i-1][k][l]+g[f[x][i-1]][i-1][l][w]);

			}

	}

	go(x)

	{

		if(tn==father)continue;

		rep(e[i],maxx,j)rep(1,e[i],k)g[tn][0][j][k]=g[tn][0][k][j]=1;

		dfs(tn,x);

	}

}

inline void LCA(int x,int y)

{

	top1=top2=0;

	if(d[x]>d[y])

	{

		fep(Log[d[x]],0,i)

		{

			if(d[f[x][i]]>=d[y])

			{

				ql[++top1]=x;

				wl[top1]=i;

				x=f[x][i];

			}

		}

	}

	if(d[y]>d[x])

	{

		fep(Log[d[y]],0,i)

		{

			if(d[f[y][i]]>=d[x])

			{

				qr[++top2]=y;

				wr[top2]=i;

				y=f[y][i];

			}

		}

	}

	if(x==y)return;

	fep(Log[d[x]],0,i)

	{

		if(f[x][i]!=f[y][i])

		{

			ql[++top1]=x;

			wl[top1]=i;

			x=f[x][i];

			qr[++top2]=y;

			wr[top2]=i;

			y=f[y][i];

		}

	}

	ql[++top1]=x;

	wl[top1]=0;

	qr[++top2]=y;

	wr[top2]=0;

}

inline void get_ans()

{

	ans=0;

	rep(1,top1,i)

	{

		rep(1,maxx,j)w[i][j]=0;

		rep(1,maxx,j)

			rep(1,j,k)w[i][j]=max(w[i][j],w[i-1][k]+g[ql[i]][wl[i]][k][j]);

	}

	int l=top2;

	rep(top1+1,top2+top1,i)

	{

		rep(1,maxx,j)w[i][j]=0;

		rep(1,maxx,j)

			rep(1,j,k)w[i][j]=max(w[i][j],w[i-1][k]+g[qr[l]][wr[l]][j][k]);

		--l;

	}

	rep(1,maxx,i)ans=max(ans,w[top1+top2][i]);

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);

	rep(2,n,i)

	{

		int x,y,z;

		get(x);get(y);get(z);

		maxx=max(maxx,z);

		add(x,y,z);add(y,x,z);

		Log[i]=Log[i>>1]+1;

	}

	dfs(1,0);

	get(m);

	rep(1,m,i)

	{

		int x,y;

		get(x);get(y);

		LCA(x,y);

		get_ans();

		put(ans);

	}

	return 0;

}

巴特西

luogu P5558 心上秋

最新文章

热门文章