题解：P12195 [NOISG 2025 Prelim] Itinerary

· · 题解

P12195 [NOISG 2025 Prelim] Itinerary

Algorithm:

树链剖分。

Solution:

赛时没切，大悲。

由于树的性质：从 u 到 v 的任意路径至少要经过其两点间最短路一次，加上我们遍历到的活动城市是要按顺序遍历的，所以我们可以猜测一个行程不合法的情况当且仅当沿着行程中相邻两点的最短路遍历的时候至少一条边被遍历了大于 2 次。

这个结论显然是正确的，因为其他在这个遍历顺序中没有遍历到的边都可以进去走一遍再出来，对结果并没有影响。

于是我们要做的就是维护路径加，全局最小值，树链剖分即可。

我们首先按顺序将活动行程中相邻两点的最短路加入，至于从不同城市出发，在活动行程的最开始加入 i 到 s_1 的最短路判断最小值是否 \le 2 即可。

赛事没切的原因是忘记树链剖分的细节了，自己的实现出现了问题。

时间复杂度：\text{O}(n \log^2 n)。

提供另外一个做法，发现这道题要做的就是将每一个城市作为活动行程的起点时，活动行程是否是以这个城市开头的欧拉序列的子序列。

所以可以直接换根 DP，但是笔者没有实现。

Code:

void read(T &x, Args &... y){read(x);read(y...);}
int n,m,ddfn;
int s[N],dfn[N],ed[N],siz[N],son[N],top[N],dep[N],fa[N];
vector<int> e[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;siz[u]=1;::fa[u]=fa;
    int mx=0;
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        if(mx<siz[v]) son[u]=v,mx=siz[v];
        siz[u]+=siz[v];
    }
    return ;
}
void dfs1(int u,int fa,int t){
    top[u]=t;dfn[u]=++ddfn;
    if(!son[u]) return ;
    dfs1(son[u],u,t);
    for(auto v:e[u]){
        if(v!=fa&&v!=son[u]) dfs1(v,u,v);
    }
    // ed[u]=ddfn;
    return ;
}
inline bool in(int x,int y){return dfn[y]<=dfn[x]&&dfn[x]<=ed[y];}
struct tree{
    int x,add;
    #define x(p) t[p].x
    #define add(p) t[p].add
}t[N*4];
#define mid (l+r>>1)
inline void update(int p){x(p)=max(x(ls),x(rs));}
inline void spread(int p){
    if(add(p)!=0){
        x(ls)+=add(p);
        x(rs)+=add(p);
        add(ls)+=add(p);add(rs)+=add(p);
        add(p)=0;
    }
    return ;
}
void addd(int p,int l,int r,int L,int R,int k){
    if(L>R) return ;
    if(L<=l&&r<=R){x(p)+=k;add(p)+=k;return ;}
    spread(p);
    if(L<=mid) addd(ls,l,mid,L,R,k);
    if(R>mid)  addd(rs,mid+1,r,L,R,k);
    update(p);
    return ;
}
int ask(int p,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l&&r<=R) return x(p);
    spread(p);
    int res=0;
    if(L<=mid) res=max(res,ask(ls,l,mid,L,R));
    if(R>mid)  res=max(res,ask(rs,mid+1,r,L,R));
    update(p);
    return res;
}
#undef x
#undef mid
#undef add
inline bool add(int x,int y,int k){
    bool res=1;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        addd(1,1,n,dfn[top[x]],dfn[x],k);
        if(ask(1,1,n,1,n)>=3) res=0;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y){
        addd(1,1,n,dfn[x]+1,dfn[y],k);
        if(ask(1,1,n,1,n)>=3) res=0;
    }
    return res;
}
signed main(){
    int st=clock();
    read(n,m);
    for(rint i=1,u,v;i<n;i++) read(u,v),e[u].pb(v),e[v].pb(u);
    dfs(1,0);ddfn=0;
    dfs1(1,0,1);
    for(rint i=1;i<=m;i++) read(s[i]);
    for(rint i=2;i<=m;i++){
        bool f=add(s[i-1],s[i],1);
        if(!f){for(rint i=1;i<=n;i++) puts("0");return 0;}
    }
    for(rint i=1;i<=n;i++){
        if(i==s[1]) puts("1");
        else{
            bool f=add(i,s[1],1);
            puts(f?"1":"0");
            add(i,s[1],-1);
        }
    }
    return 0;
}