• 周二. 10 月 8th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客暑期多校训练营7

admin

11 月 28, 2021

F xay loves trees

很快找到两道签到题。因为是一场快乐的比赛中,结果就被卡住了。

显然这个集合在第一棵树上是一条链(链中点的深度连续递减)。

然后考虑第二棵树的限制,可以求出第二棵树每个点的欧拉序。有祖先的关系就是欧拉序包含。

然后就是求,第一棵树上满足在第二棵树上欧拉序不相交的最长链。

进一步,就是给每个点一个去间,求一个树上一个最长链似的其包含点对应的区间不相交。

考虑用主席树维护一个点到根所有点的区间和。

然后每个点x记录以这个点为链最深的点时,这条链满足条件且最长时深度最浅的点top[x]。

然后求以点u为链最深的点时的答案是,就是在fa[u]和fa[top[u]]中间倍增找到最浅的u对应区间和为0的点。

当时想到正解了,但是区间加的主席树不会写(其实就是不用lazy标记的洛谷模板—线段树模板1)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 301000
#define int long long
int read(){
	int sum=0,f=1;char ch=getchar();
	ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int n,ans;
int cnt_1,head_1[N],cnt_2,head_2[N];
struct edge1{
	int to,nxt;
}e_1[N*2];
void add_edge_1(int u,int v){
	cnt_1++;
	e_1[cnt_1].nxt=head_1[u];
	e_1[cnt_1].to=v;
	head_1[u]=cnt_1;
}
struct edge2{
	int to,nxt;
}e_2[N*2];
void add_edge_2(int u,int v){
	cnt_2++;
	e_2[cnt_2].nxt=head_2[u];
	e_2[cnt_2].to=v;
	head_2[u]=cnt_2;
}
int L[N],R[N];
int fa[N][22],dep[N],tot;
void get_fa(int u,int f,int deep){
	fa[u][0]=f;dep[u]=deep;
	for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head_1[u];i;i=e_1[i].nxt){
		int v=e_1[i].to;
		if(v==f)continue;
		get_fa(v,u,deep+1);
	}
}
void get_dfn(int u,int f,int deep){
	L[u]=++tot;
	for(int i=head_2[u];i;i=e_2[i].nxt){
		int v=e_2[i].to;
		if(v==f)continue;
		get_dfn(v,u,deep+1);
	}
	R[u]=tot;
}
int sum[N*40],ch[N*40][2],root[N],lazy[N*40],top[N];
void build(int L,int R,int &now){
	now=++tot;
	sum[now]=0;
	ch[now][0]=ch[now][1]=0;
	lazy[now]=0;
	if(L==R)return;
	int mid=(L+R>>1);
	build(L,mid,ch[now][0]);
	build(mid+1,R,ch[now][1]);
}
void add(int L,int R,int l,int r,int pre,int &now){
	now=++tot;
	ch[now][0]=ch[pre][0];
	ch[now][1]=ch[pre][1];
	sum[now]=sum[pre];
	lazy[now]=lazy[pre];
	sum[now]+=r-l+1;
	if(l==L&&R==r){
		lazy[now]+=1;
		return ;
	}
	int mid=(L+R>>1);
	if(l>mid)add(mid+1,R,l,r,ch[pre][1],ch[now][1]);
	else if(r<=mid)add(L,mid,l,r,ch[pre][0],ch[now][0]);
	else add(L,mid,l,mid,ch[pre][0],ch[now][0]),add(mid+1,R,mid+1,r,ch[pre][1],ch[now][1]); 
} 
int check(int L,int R,int l,int r,int pre,int now){
	if(l==L&&R==r){
		return sum[now]-sum[pre];
	}
	int mid=(L+R>>1);
	if(l>mid)return check(mid+1,R,l,r,ch[pre][1],ch[now][1])+(lazy[now]-lazy[pre])*(r-l+1);
	else if(r<=mid)return check(L,mid,l,r,ch[pre][0],ch[now][0])+(lazy[now]-lazy[pre])*(r-l+1);
	else return check(L,mid,l,mid,ch[pre][0],ch[now][0])+check(mid+1,R,mid+1,r,ch[pre][1],ch[now][1])+(lazy[now]-lazy[pre])*(r-l+1); 
}
void build_tree(int u,int f){
	add(1,n,L[u],R[u],root[fa[u][0]],root[u]);
	for(int i=head_1[u];i;i=e_1[i].nxt){
		int v=e_1[i].to;
		if(v==f)continue;
		build_tree(v,u);
	}
}
void get_ans(int u,int f){
	if(u==1)ans=1,top[u]=u;
	else{
		int now=u;
		for(int i=20;i>=0;i--){
			int x=fa[fa[now][i]][0],y=fa[u][0];
			if(dep[x]+1<dep[top[y]])continue;
			if(check(1,n,L[u],R[u],root[x],root[y])==0)now=fa[now][i];
		}
		top[u]=now;
		ans=max(ans,dep[u]-dep[now]+1-(now==0?1:0));
	}
	for(int i=head_1[u];i;i=e_1[i].nxt){
		int v=e_1[i].to;
		if(v==f)continue;
		get_ans(v,u);
	}
} 
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n); 
		cnt_1=cnt_2=0;
		for(int i=1;i<=n;i++)head_2[i]=head_1[i]=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=20;j++)fa[i][j]=0;
		for(int i=2;i<=n;i++){
			int x,y;
			scanf("%lld%lld",&x,&y); 
			add_edge_1(x,y);
			add_edge_1(y,x); 
		}
		for(int i=2;i<=n;i++){
			int x,y;
			scanf("%lld%lld",&x,&y);
			add_edge_2(x,y);
			add_edge_2(y,x); 
		}
		tot=0;
		get_dfn(1,0,1);
		get_fa(1,0,1);
		tot=0;
		for(int i=0;i<=n;i++)root[i]=0,top[i]=0;
		build(1,n,root[0]);
		build_tree(1,0);
		ans=0;
		get_ans(1,0);
		printf("%lld
",ans);
	}
	return 0;
}

发表回复