P12195题解

题意：

给出一棵树以及一个序列

s

，对于每一个节点，回答是否存在一个以该点为起点的欧拉序

e

，使得

s

是

e

的子序列。

n\le 2\times10^5,|s|<2n

。

Sol：

考虑模拟：从

i

出发，每次走到

s

的下一个点，如果经过一条走过的边就无解。
我们发现，如果以

i

为根，且对于每个

x

，

x

子树内的点在

s

中出现的位置都是连续的即可。
于是有一个

O(n^2)

做法：求出

x

子树内的点在

s

中最先、最后出现的位置以及总次数，如果

\forall x,R_x-L_x=cnt_x

，则合法。

然后考虑换根。当根从

i

变成一个相邻的点

j

时，只有

i,j

的子树发生变化。假设

i=fa_j

，则

i

的子树变成了除

j

子树以外的所有点。那么子树

i

在

s

内连续，等价于

j

在

s

中恰好占据开头一段和结尾一段。于是我们求出

j

在

s

的开头、结尾最长的连续长度，判断加起来是否等于

cnt_j

即可。我们对

dfn_{s_i}

做前、后缀

\min,\max

即可线性求得，见代码。

总复杂度

O(n)

。

Code：

CPP

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 4e5 + 5;
int n,m,tot,num,s[N],cnt[N],L[N],R[N],siz[N],dfn[N],rev[N],f[N];
int L1[N],L2[N],R1[N],R2[N],ans[N];
vector <int> v[N];
void upd(int x,int v){num += v - f[x],f[x] = v;}
void dfs1(int x,int lst)
{
	siz[x] = 1,dfn[x] = ++tot,rev[tot] = x;
	for(int y : v[x])
	{
		if(y == lst) continue;
		dfs1(y,x);
		cnt[x] += cnt[y];
		if(L[y]) L[x] = min(L[x],L[y]),R[x] = max(R[x],R[y]);
		siz[x] += siz[y];
	}
}
void dfs2(int x,int lst)
{
	ans[x] = (num == n);
	for(int y : v[x])
	{
		if(y == lst) continue;
		upd(x,min(L1[dfn[y]],L2[dfn[y] + siz[y] - 1]) + min(R1[dfn[y]],R2[dfn[y] + siz[y] - 1]) >= cnt[y]),upd(y,1);
		dfs2(y,x);
		upd(x,1),upd(y,L[y] > R[y] || cnt[y] == R[y] - L[y] + 1);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1,a,b;i < n;i++)
	{
		scanf("%d%d",&a,&b);
		v[a].pb(b),v[b].pb(a);
	}
	for(int i = 1;i <= m;i++) scanf("%d",&s[i]);
	for(int i = 1;i <= m;i++) cnt[s[i]]++;
	for(int i = 1;i <= n;i++) L[i] = m;
	for(int i = m;i >= 1;i--) L[s[i]] = i;
	for(int i = 1;i <= m;i++) R[s[i]] = i;
	dfs1(1,0);
	for(int i = 1;i <= n;i++) upd(i,L[i] > R[i] || cnt[i] == R[i] - L[i] + 1);
	for(int i = 1;i <= n;i++) L1[i] = L2[i] = R1[i] = R2[i] = m;
	for(int i = 1,minn = n,maxn = 0,t1 = n,t2 = 1;i <= m;i++)
	{
		minn = min(minn,dfn[s[i]]),maxn = max(maxn,dfn[s[i]]);
		while(t1 > minn) L1[t1--] = i - 1;
		while(t2 < maxn) L2[t2++] = i - 1;
	}
	for(int i = m,minn = n,maxn = 0,t1 = n,t2 = 1;i >= 1;i--)
	{
		minn = min(minn,dfn[s[i]]),maxn = max(maxn,dfn[s[i]]);
		while(t1 > minn) R1[t1--] = m - i;
		while(t2 < maxn) R2[t2++] = m - i;
	}
	dfs2(1,0);
	for(int i = 1;i <= n;i++) printf("%d\n",ans[i]);
	return 0;
}

文章操作

题意：

Sol：

Code：

相关推荐

评论

P12195题解