P12195 [NOISG 2025 Prelim] Itinerary

· · 题解

倍增 lca 题解

题目要求每条边最多走两次，s 中的点必须按顺序被遍历，问从每一个点出发能否按照要求遍历

判断是否有一种行程满足要求，先从 s_1 按 s_i 顺序遍历一遍，当搜索到 u 时，求 s_i 与 u 的 lca。若 lca 为 u，则从 s_i 倍增到 u 的儿子,递归它；若不是，则 s_i 不在 u 的子树中，返回到 fa_u。递归和返回时都增加边的经过次数，超过2则答案全为0。边的经过次数用 map<pair,int> 统计。

再从 s_1 向外 dfs ,若一条边 u-v 被走过 一次及以下 ，则 dfs(v,u)，每到一个点打标记。最终标记点都能够到达 s_1。\ 时间复杂度 O(n\log n) 

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m;
const int N=2e5+5;
int f[N][25],dep[N];
vector<int>vc[N];
int a[2*N];
map<int,int>cnt;
int p=1;
int vis[N];
map<pair<int,int>,int>mp; //存u-v边走的次数 
pair<int,int> pr(int u,int v){
    return make_pair(max(u,v),min(u,v));
}
void dfs1(int u,int fa){//倍增板子 
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=21;i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int v:vc[u]){
        if(v==fa)continue;
        dfs1(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
    }
    if(x==y)return x;
    for(int i=21;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int gs(int x,int y){//x跳到y走向x方向的儿子 
    if(dep[x]<dep[y])swap(x,y);
    for(int i=21;i>=0;i--){
        if(dep[f[x][i]]>dep[y])x=f[x][i];
    }
    return x;
}
void dfs2(int u,int fa){
    while(p<=m){
        if(u==a[p])p++;
        if(p>m)return;
        int l=lca(u,a[p]);
        if(l==u){//目标在x子树内，向下dfs
            int s=gs(a[p],u);//找出正确的儿子 
            mp[pr(u,s)]++;//从u走到s 
            if(mp[pr(u,s)]>=3){//判断路径是否超过2次 
                for(int i=1;i<=n;i++){//不然会T，下同 
                    cout<<0<<'\n';
                }
                exit(0);
            }
            dfs2(s,u);
            if(p>m)return;
        }
        else{
            mp[pr(u,fa)]++;//目标不在x子树内，向上dfs
            if(mp[pr(u,fa)]>=3){//下同 
                for(int i=1;i<=n;i++){
                    cout<<0<<'\n';
                }
                exit(0);
            }
            return;
        }
    }
    mp[pr(u,fa)]++;
    if(mp[pr(u,fa)]>=3){
        for(int i=1;i<=n;i++){
            cout<<0<<'\n';
        }
        exit(0);
    }
}
void dfs3(int u,int fa){
    vis[u]=1;
    for(int v:vc[u]){//边数<2的可以再走一遍 
        if(v==fa||(mp.count(pr(u,v))&&mp[pr(u,v)]>=2))continue;
        dfs3(v,u);
    }
}
signed main(){
    ios::sync_with_stdio(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        vc[u].pb(v);
        vc[v].pb(u);
    }
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    dfs1(a[1],0);
    dfs2(a[1],0);
    dfs3(a[1],0);
    for(int i=1;i<=n;i++){
        cout<<vis[i]<<'\n';
    }
    return 0;
}