题解：P11162 [BalkanOI 2023] Car Race

· · 题解

首先只有相同深度的赛车可能相遇。考虑 dfs 一遍，然后在这个过程中记录每个点上一个与它深度相同的点以及它们的 LCA。LCA 可以用 tarjan 做到 O(n\alpha(n))，也可以做到线性。

然后考虑按发生时间先后处理碰撞，相同深度的 2 点 i,j 的 LCA 的深度就是区间 min，所以可以每层一个链表维护还存在的节点，然后用优先队列维护目前最早的相遇即可，O(n\log n)。可以把优先队列换成桶，O(n)。

#include <bits/stdc++.h>
using namespace std;
int n,f[1000005],a[1000005],fd[1000005],dep[1000005],last[1000005],lst[1000005],nxt[1000005],pre[1000005];
vector<int> g[1000005],tag[1000005];
int find(int x){
    return fd[x]?fd[x]=find(fd[x]):x;
}
void dfs(int x){
    lst[x]=last[dep[x]],last[dep[x]]=x,nxt[x]=n+1;
    if(lst[x]){
        if(!a[lst[x]]) lst[x]=lst[lst[x]];
        nxt[lst[x]]=x;
        if(lst[x]){
            pre[x]=dep[find(lst[x])];
            if(a[x]) tag[pre[x]].push_back(x);
        }
    }
    for(int v:g[x])
        dfs(v);
    fd[x]=f[x];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n,nxt[n+1]=n+1;
    for(int i=2;i<=n;i++)
        cin>>f[i],f[i]++,dep[i]=dep[f[i]]+1,g[f[i]].push_back(i);
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1);
    for(int i=1;i<=n;i++)
        if(!a[nxt[i]])
            nxt[i]=n+1;
    int mx=n;
    while(1){
        while(mx&&!tag[mx].size()) mx--;
        if(!mx) break;
        int u=tag[mx].back();
        tag[mx].pop_back();
        if(pre[u]<mx) continue;
        int l=lst[u],r=u;
        a[u]=a[l]=pre[u]=0;
        while(r<=n&&pre[nxt[r]]==mx) r=nxt[r],pre[r]=0,a[r]=0;
        while(l&&pre[l]==mx) pre[l]=0,l=lst[l],a[l]=0;
        pre[nxt[r]]=min(pre[nxt[r]],pre[l]),pre[l]=0,tag[pre[nxt[r]]].push_back(nxt[r]);
        lst[nxt[r]]=lst[l],nxt[lst[l]]=nxt[r];
    }
    for(int i=1;i<=n;i++)
        cout<<(a[i]?dep[i]:-1)<<' ';
    cout<<'\n';
    return 0;
}
/*
10
0 0 2 2 4 4 6 3 6 
0 0 1 0 0 1 1 1 1 1 
*/