P12195

· · 题解

题目大意

给定一棵 n 个点的树和一个点的序列 s，要求按顺序访问序列中的所有点，并且树上每条边要被访问恰好 2 次。问每个点是否能作为起点。

sol

首先指定 1 为树根，把所有 s_i\to s_{i+1}(1\le i < m) 的路径取出，构成一个极小联通块。我们发现不管怎么走，在事件 i 和 i+1 发生之间，s_i\to s_{i+1} 的最短路径上的边一定都会被访问至少一次，于是我们可以通过树剖计算出每条边至少要被访问几次。如果有任何一条边被访问了 \ge 3 次，那么从任何一个点开始都无法成功构成一个巡游。

然后我们把选择的起点加上，也就是 S\to s_1 的最短路径上所有边都会至少被访问 1 次。很容易发现如果要满足每条边访问不超过 2 次，那么 S 只能从能被 s_1 通过最少访问次数为 0,1 的边遍历到的联通块中选取。

接下来我们来证明此时这个联通块中所有点都能作为起始点。

我们取出 S\to s_1,s_1\to s_2,\dots,s_{m-1}\to s_m 这 m 条路径所构成的联通块，则这个联通块上每条边的最少访问次数均为 1 或 2，每个点都至少被遍历了一次。

联通块内每个点 u 第一次遍历到时，都将其不在联通块内的子树全部遍历完成，容易知道这是可行的。而在联通块内，取出 S\to s_1,s_1\to s_2,\dots,s_{m-1}\to s_m,s_m\to S 这 m+1 条路径，容易发现这构成了一个 dfs 序。所以只需要按照这个顺序进行遍历，并在遍历到一个点时处理好其所有不在联通块内的子树即可。

所以只需要：

答案就是联通块的大小。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>G[200005];
vector<pair<int,int> >E[200005];
struct node{
    int len,w,lz;
}tr[800005];
int n,m,cnt,a[200005],b[200005];
int dis[200005],fa[200005],son[200005],siz[200005],tp[200005],idx[200005],ans[200005];
void dfs1(int u,int f){
    dis[u]=dis[f]+1;
    fa[u]=f,siz[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void pushup(int x){
    tr[x].w=tr[x<<1].w+tr[x<<1|1].w;
}
void Build(int x,int l,int r){
    tr[x].len=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
    pushup(x);
}
void dfs2(int u,int top){
    idx[u]=++cnt;
    a[cnt]=b[u];
    tp[u]=top;
    if(!son[u]) return ;
    dfs2(son[u],top);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(idx[v])continue;
        dfs2(v,v);
    }
}
void pushdown(int x){
    if(!tr[x].lz) return ;
    tr[x<<1].w=(tr[x<<1].w+tr[x<<1].len*tr[x].lz);
    tr[x<<1|1].w=(tr[x<<1|1].w+tr[x<<1|1].len*tr[x].lz);
    tr[x<<1].lz=(tr[x<<1].lz+tr[x].lz);
    tr[x<<1|1].lz=(tr[x<<1|1].lz+tr[x].lz);
    tr[x].lz=0;
}
void upd(int x,int l,int r,int L,int R,int val){
    if(R<L)return;
    if(L<=l&&r<=R){
        tr[x].w+=tr[x].len*val;
        tr[x].lz+=val;
        return ;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(L<=mid)upd(x<<1,l,mid,L,R,val);
    if(R>mid)upd(x<<1|1,mid+1,r,L,R,val);
    pushup(x);
}
void TreeAdd(int x,int y){
    while(tp[x]!=tp[y]){
        if(dis[tp[x]]<dis[tp[y]]) swap(x,y);
        upd(1,1,n,idx[tp[x]],idx[x],1);
        x=fa[tp[x]];
    }
    if(dis[x]>dis[y]) swap(x,y);
    upd(1,1,n,idx[x]+1,idx[y],1);
}
void dfs(int u,int f){
    ans[u]=1;
    for(int i=0;i<E[u].size();i++){
        int v=E[u][i].first,w=E[u][i].second;
        if(v==f||w>1)continue;
        dfs(v,u);
    }
}
int query(int x,int l,int r,int ps){
    if(l==r)return tr[x].w;
    pushdown(x);
    int mid=(l+r)>>1,ans=0;
    if(ps<=mid)return query(x<<1,l,mid,ps);
    else return query(x<<1|1,mid+1,r,ps);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    Build(1,1,n);
    cin>>b[1];
    for(int i=2;i<=m;i++){
        cin>>b[i];
        TreeAdd(b[i-1],b[i]);
    }
    for(int i=2;i<=n;i++){
        int w=query(1,1,n,idx[i]);
        if(w>2){
            for(int i=1;i<=n;i++)cout<<"0\n";
            return 0;
        }
        E[fa[i]].push_back({i,w});
        E[i].push_back({fa[i],w});
    }
    dfs(b[1],-1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
}