题解：P12195 [NOISG 2025 Prelim] Itinerary

SunburstFan · 2025-05-10 11:13:06 · 题解

P12195 [NOISG 2025 Prelim] Itinerary

题目大意

有一个树和一个序列，要求按照给出的顺序访问序列中的所有点，问每个点能否作为起点。

解题思路

如果一个方案不合法，当且仅当沿着这个方案中相邻两个点的最短路遍历的时候有一条边被遍历了大于 2 边。

考虑树链剖分，将相邻两点的最短路加入，对于从城市 i 出发，在活动行程的最开始加入 i 到 s_i 的最短路判断最小值是否 \le 2。

时间复杂度 O(N\times \log ^2 N)。

namespace SGT{
    #define int long long
    const int N = 1e5+5;

    #define lson rt<<1,l,md
    #define rson rt<<1|1,md+1,r

    int xds[N<<4],tag[N<<4];

    void push_up(int rt){
        xds[rt]=max(xds[rt<<1],xds[rt<<1|1]);
    }

    void build(int rt,int l,int r){
        if(l==r){
            xds[rt]=a[l];
            return;
        }
        int md=(l+r)>>1;
        build(lson),build(rson);
        push_up(rt);
    }

    void push_down(int rt){
        if(tag[rt]){
            xds[rt<<1]+=tag[rt];
            xds[rt<<1|1]+=tag[rt];
            tag[rt<<1]+=tag[rt];
            tag[rt<<1|1]+=tag[rt];
            tag[rt]=0;
        }
    }

    void update(int rt,int l,int r,int L,int R,int x){
        if(L<=l&&r<=R){
            xds[rt]+=x;
            tag[rt]+=x;
            return;
        }
        push_down(rt);

        int md=(l+r)>>1;
        if(L<=md)update(lson,L,R,x);
        if(R>md)update(rson,L,R,x);
        push_up(rt);
    }

}

namespace sunburstfan{
    const int N=2e5+5;

    int n,m;
    int sz[N],dep[N],fa[N],son[N],top[N],dfn[N],rnk[N],cnt;
    vector<int> G[N];

    void dfs1(int u,int f){
        sz[u]=1,fa[u]=f,dep[u]=dep[f]+1;
        for(int v:G[u]){
            if(v==f)continue;
            dfs1(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]])son[u]=v;
        }
    }

    void dfs2(int u,int t){
        top[u]=t,dfn[u]=++cnt,rnk[cnt]=u;
        if(!son[u])return;
        dfs2(son[u],t);
        for(int v:G[u]){
            if(v==fa[u]||v==son[u])continue;
            dfs2(v,v);
        }
    }

    int LCA(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            x=fa[top[x]];
        }
        return dep[x]<dep[y]?x:y;
    }

    void update(int u,int v,int k){
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            SGT::update(1,1,n,dfn[top[u]],dfn[u],k);
            u=fa[top[u]];
        }
        if(dep[u]<dep[v])swap(u,v);
        SGT::update(1,1,n,dfn[v]+1,dfn[u],k);
    }

    void solve(){
        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);
        for(int i=1;i<=m;i++){
            cin>>a[i];
        }
        for(int i=1;i<m;i++){
            update(a[i],a[i+1],1);
        }
        for(int i=1;i<=n;i++){
            update(i,a[1],1);
            if(SGT::xds[1]<=2)cout<<1<<"\n";
            else cout<<0<<"\n";
            update(i,a[1],-1);
        }

        return;
    }
}