P12195题解

allenchoi · 2025-09-05 16:08:43 · 题解

题意：

给出一棵树以及一个序列 s，对于每一个节点，回答是否存在一个以该点为起点的欧拉序 e，使得 s 是 e 的子序列。

\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：

#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;
}