列表

详情

NC212177. brz的扑克

描述

赌神 送了蒟蒻 一棵扑克树，树的每个点上都放了一张扑克，扑克有正反两面，两面上分别写了两个不同的数字。

但是赌神 提了个要求：你要能回答我的问题才能拥有这棵扑克树。

赌神 提出了 m 个问题，每个问题包含两个整数 x,y，表示依次取出 x 到 y 路径上的扑克排列成一行，可以随意将扑克进行翻转，最后所有扑克朝上的那一面的数字就形成了一个序列，赌神 问你：所有可能的序列中包含的最长顺子的长度是多少？

赌神 对顺子的定义是：1、顺子是序列中的一个连续区间 [l,r]；2、设区间最左边的数是 z，那么后面的数依次是 z+1,z+2,...,z+r-l。比如说一个序列 {1,3,4,5,7,6,7}，有这些顺子：[1,1],[2,4],[5,5],[6,7]。当然，[2,3] 也是一个顺子，但是他被 [2,4] 包含所以不可能成为最长的顺子，所以可以忽略掉。

（看起来似乎有点抽象，你可以结合样例来理解）

输入描述

第一行一个整数 n，表示树的大小。

下面 n 行每行两个整数，第 i 行的两个数分别表示第 i 个节点上的扑克的正反两面上的数字。

下面 n-1 行每行两个整数 x,y，表示节点 x 与节点 y 之间有一条边。

下面一行一个整数 m 表示询问数量。

下面 m 行每行两个整数 x,y，表示一次询问，注意，询问之间相互独立，即每次询问完后会把扑克放回树上的原位置。


 扑克上的数字 。

输出描述

输出 m 行每行一个数，第 i 行的数表示第 i 组询问能找到的最长顺子的长度。

示例1

输入: 

6
2 4
1 3
1 2
3 4
5 6
7 8
1 2
2 3
2 4
1 5
5 6
2
3 4
2 6

输出: 

3
3

说明:

样例的树长这样：



对于第一组询问，取出 3 到 4 路径上的扑克得到的扑克序列为 (1,2),(1,3),(3,4)，让第一张数字 2 朝上，第二张 3 朝上，第三张 4 朝上，最后得到的序列就是 2,3,4，最长顺子就是 2,3,4，长度为 3。

对于第二组询问，扑克序列为 (1,3),(2,4),(5,6),(7,8)，可以得到的序列之一是 3,4,5,7，最长顺子为 3,4,5 长度为 3，可以证明不存在更长的顺子。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 375ms, 内存消耗: 17784K, 提交时间: 2020-11-10 21:14:43 

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+9;
int n,m,num=0,root;
int head[M],ma[M],siz[M],va[M][2];
struct P{int to,ne;}e[M<<1];
struct Q{int y,id,o;};
vector<Q>g[M];
int in[M],kind[M],val[M][2],ans[M],up[M][2][2],dw[M][2][2];
int li[M][2],ri[M][2];
bool vis[M];
int read(){
	int rex=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){rex=rex*10+ch-'0';ch=getchar();}
	return rex*f;
}
void findroot(int u,int fa,int sum){
	ma[u]=0,siz[u]=1;
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to;
		if(v!=fa&&!vis[v]){
			findroot(v,u,sum);
			siz[u]+=siz[v];
			ma[u]=max(ma[u],siz[v]);
		}
	}
	ma[u]=max(ma[u],sum-siz[u]);
	if(ma[u]<ma[root])root=u;
}
void solve(int u,int fa,int o,int deep){
	int mi[2];kind[u]=o;in[u]=root;
	mi[0]=mi[1]=0;
	for(int i=0;i<=1;++i){
		for(int j=0;j<=1;++j)
			up[u][i][j]=up[fa][i][j],
			dw[u][i][j]=dw[fa][i][j];
		if(fa!=root)
		for(int j=0;j<=1;++j)
		for(int k=0;k<=1;++k){
			if(up[fa][j][k]==deep&&va[u][i]==va[fa][j]+1)up[u][i][k]=deep+1;
			if(dw[fa][j][k]==deep&&va[u][i]==va[fa][j]-1)dw[u][i][k]=deep+1;
		}
		else {
			for(int j=0;j<=1;++j){
				if(va[u][i]==va[fa][j]+1)up[u][i][j]=2;
				if(va[u][i]==va[fa][j]-1)dw[u][i][j]=2;
			}
		}
	}
	for(int i=0;i<=1;++i){
		li[u][i]=ri[u][i]=1;
		for(int j=0;j<=1;++j){
			if(va[u][i]==va[fa][j]+1)li[u][i]=max(li[u][i],li[fa][j]+1);
			if(va[u][i]==va[fa][j]-1)ri[u][i]=max(ri[u][i],ri[fa][j]+1);
		}
		mi[0]=max(mi[0],li[u][i]);
		mi[1]=max(mi[1],ri[u][i]);
	}
	mi[0]=max(mi[0],val[fa][0]);
	mi[1]=max(mi[1],val[fa][1]);
	val[u][0]=mi[0];
	val[u][1]=mi[1];
	for(int i=0,s=g[u].size();i<s;++i){
		int v=g[u][i].y,id=g[u][i].id,x=g[u][i].o;
		if(kind[v]!=kind[u]&&in[v]==root){
			if(x==1)ans[id]=max(val[u][1],val[v][0]);
			else ans[id]=max(val[u][0],val[v][1]);
			for(int j=0;j<=1;++j)
			for(int k=0;k<=1;++k)
			for(int l=0;l<=1;++l){
				if(x==-1)ans[id]=max(ans[id],up[u][j][l]+dw[v][k][l]-1);
				else ans[id]=max(ans[id],dw[u][j][l]+up[v][k][l]-1);
			}
		}
	}
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to;
		if(v!=fa&&!vis[v])solve(v,u,o,deep+1);
	}
}
void dfs(int u,int sum){
	root=0;
	findroot(u,0,sum);
	u=root;
	val[u][0]=val[u][1]=vis[u]=1;
	in[u]=u;
	kind[u]=0;
	for(int i=0;i<=1;++i)li[u][i]=ri[u][i]=1;
	for(int i=0;i<=1;++i)
	for(int j=0;j<=1;++j)
		up[u][i][j]=dw[u][i][j]=1;
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to;
		if(!vis[v])solve(v,u,v,1);
	}
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to;
		if(!vis[v])dfs(v,siz[v]);
	}
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("m.txt","w",stdout); 
	n=read();
	for(int i=1;i<=n;++i)va[i][0]=read(),va[i][1]=read();
	for(int i=1,x,y;i<n;++i){
		x=read(),y=read();
		e[++num]=P{y,head[x]};head[x]=num;
		e[++num]=P{x,head[y]};head[y]=num;
	}
	m=read();
	for(int i=1,x,y;i<=m;++i){
		x=read(),y=read();
		g[x].push_back(Q{y,i,1});
		g[y].push_back(Q{x,i,-1});
		if(x==y)ans[i]=1;
	}
	ma[0]=1e9;
	dfs(1,n);
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}

上一题

© 2024 nowcoder.com