题解：P12195 [NOISG 2025 Prelim] Itinerary

AC_Lover · 2025-09-06 23:12:38 · 题解

P12195 [NOISG 2025 Prelim] Itinerary

这里是一个 O(n) 的换根做法。

简要题意： 对于每个点作为根，分别求出是否存在一个欧拉序满足关键点序列是其子序列。

解法：

先考虑对一个特定点作根判断存在性。注意到如果已经离开了某个子树，那么后面是不能再进入这个子树了，所以连续在一起的关键点一定要在这棵子树的遍历中一并被解决，换言之，任意子树中关键点在原序列中的位置构成一个区间，不难发现这与每个根是否合法等价。而判断是否在一个区间内是简单的，只需要求出子树中编号最小值、最大值、关键点个数，判断区间是否被填满即可。因此可以对每个点都跑一遍，时间复杂度 O(n^2)。

:::info[O(n^2)]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define psb push_back
#define SZ(vec) ((int)vec.size())

using namespace std;

template<class T>void Max(T &x,T y) { if (y>x) x=y; }
template<class T>void Min(T &x,T y) { if (y<x) x=y; }
const int N=200010;
int n,m;
int h[N],e[N<<1],ne[N<<1],idx;
void add(int u,int v) { e[idx]=v,ne[idx]=h[u],h[u]=idx++; }
int pl[N],pr[N],eff[N];
int sz[N];
bool sub[N],in[N];
int imi[N],imx[N];

void dfs_in(int u,int fat)
{
    imi[u]=pl[u],imx[u]=pr[u];
    sz[u]=eff[u];
    sub[u]=true; in[u]=true;
    for (int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if (v==fat) continue;
        dfs_in(v,u);
        Min(imi[u],imi[v]);
        Max(imx[u],imx[v]);
        sz[u]+=sz[v];
        sub[u] &= sub[v];
        in[u] &= sub[v];
    }
    sub[u] &= (imi[u]>imx[u] || (imx[u]-imi[u]+1==sz[u]));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    memset(h,-1,sizeof(h));
    for (int i=1;i<n;i++) 
    {
        int u,v;
        cin >> u >> v;
        add(u,v);
        add(v,u);
    }

    for (int i=1;i<=n;i++) { pl[i]=1e9,pr[i]=0; }
    for (int i=1;i<=m;i++)
    {
        int x;
        cin >> x;
        Min(pl[x],i);
        Max(pr[x],i);
        eff[x]++;
    }

    for (int i=1;i<=n;i++)
    {
        dfs_in(i,0);
        cout << in[i] << "\n";
    }

    return 0;
}

:::

考虑用换根优化，考察一个点 u 做为根时的子树，就是下图所示的部分：

用 out_u 表示点 u 子树外的部分，u 的子树包括 out_{\mathrm{fa}_u} 和 son_u 两部分，其中 son_u 已经在求子树内信息是被处理过，而 out_{\mathrm{fa}_u} 在换根时已经知道状态，因此可以直接计算出 u 的合法性。

然后考虑从 u 转移到其某个子树 v。son_v 已经知道，需要处理的就是从 u 到 v 的过程中外部增加的子树，不难发现就是原图中的绿色部分，因此再加上这部分的限制即可，实现时为了高效可以先处理出一个前后缀，到某个子树就是前后缀拼接的结果，每次换根可以做到 O(1)，总时间复杂度 O(n)。

:::info[O(n)]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define psb push_back
#define SZ(vec) ((int)vec.size())

using namespace std;

template<class T>void Max(T &x,T y) { if (y>x) x=y; }
template<class T>void Min(T &x,T y) { if (y<x) x=y; }
const int N=200010;
int n,m;
int h[N],e[N<<1],ne[N<<1],idx;
void add(int u,int v) { e[idx]=v,ne[idx]=h[u],h[u]=idx++; }
int pl[N],pr[N],eff[N];
int sz[N];
bool sub[N],in[N];
int imi[N],imx[N];
int ex[N];

void dfs_in(int u,int fat)
{
    imi[u]=pl[u],imx[u]=pr[u],sz[u]=eff[u];
    sub[u]=true; in[u]=true;
    for (int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if (v==fat) continue;
        dfs_in(v,u);
        Min(imi[u],imi[v]);
        Max(imx[u],imx[v]);
        sz[u]+=sz[v];
        sub[u] &= sub[v];
        in[u] &= sub[v];
    }
    sub[u] &= (imi[u]>imx[u] || (imx[u]-imi[u]+1==sz[u]));
}

int mi[N],mx[N];
int out[N];
void dfs_out(int u,int fat,bool up)
{
    //cout << u << " " << mi[u] << " " << mx[u] << " " << up << "\n";
    out[u]=up && (mi[u]>mx[u] || mx[u]-mi[u]+1==m-sz[u]);
    vector<int> son;
    for (int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if (v==fat) continue;
        son.psb(v);
    }
    vector<int> pmi(SZ(son),1e9),pmx(SZ(son),0),ps(SZ(son),1);
    for (int i=0;i<SZ(son);i++) 
    {
        if (i) 
        {
            pmi[i]=pmi[i-1];
            pmx[i]=pmx[i-1];
            ps[i]=ps[i-1];
        }
        Min(pmi[i],imi[son[i]]);
        Max(pmx[i],imx[son[i]]);
        ps[i] &= sub[son[i]];
    }
    vector<int> smi(SZ(son),1e9),smx(SZ(son),0),ss(SZ(son),1);
    for (int i=SZ(son)-1;i>=0;i--)
    {
        if (i!=SZ(son)-1) 
        {
            smi[i]=smi[i+1];
            smx[i]=smx[i+1];
            ss[i]=ss[i+1];
        }
        Min(smi[i],imi[son[i]]);
        Max(smx[i],imx[son[i]]);
        ss[i] &= sub[son[i]];
    }

    for (int i=0;i<SZ(son);i++)
    {
        int v=son[i];

        Min(mi[v],mi[u]);Max(mx[v],mx[u]);
        Min(mi[v],pl[u]);Max(mx[v],pr[u]);

        bool flag=true;
        if (i>0) 
        {
            Min(mi[v],pmi[i-1]);
            Max(mx[v],pmx[i-1]);
            flag &= ps[i-1];
        }
        if (i<SZ(son)-1) 
        {
            Min(mi[v],smi[i+1]);
            Max(mx[v],smx[i+1]);
            flag &= ss[i+1];
        }
        dfs_out(v,u,out[u] && flag);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    memset(h,-1,sizeof(h));
    for (int i=1;i<n;i++) 
    {
        int u,v;
        cin >> u >> v;
        add(u,v);
        add(v,u);
    }
    for (int i=0;i<=n;i++) { pl[i]=mi[i]=1e9,pr[i]=mx[i]=0; }
    for (int i=1;i<=m;i++)
    {
        int x;
        cin >> x;
        Min(pl[x],i); Max(pr[x],i);
        eff[x]++;
    }
    dfs_in(1,0);
    dfs_out(1,0,1);
    for (int i=1;i<=n;i++) cout << (in[i] && out[i]) << "\n";

    //for (int i=1;i<=n;i++) cout << in[i] << " " << out[i] << "\n";

    return 0;
}

:::