一起找不同

样例输入

10 6
1 2 1 4 4 6 7 2 9
1 4
3 6
3 7
9 4
5 10
3 4

样例输出

0 2 2 1 -1 3 3 -1 2 -1

//我的TLE 25分
#include<bits/stdc++.h>
#define fre(o) freopen(#o".in","r",stdin),freopen(#o".out","w",stdout)
#define ad(k) (k=-~k)
#define sb(k) (k=~-k)
#define F(i,a,b) for(register int i=a;i<=b;i=-~i)
using namespace std;const int N=500005;
vector<int> a[N],b[N];queue<int> qu;
int n,m,q,p,father[N],c[N],d[N],e[N],ans[N];
inline void build(const int id,const int sd){
    d[id]=sd;
    F(i,0,a[id].size()-1)if(a[id][i]!=father[id]){father[a[id][i]]=id;build(a[id][i],sd+1);}
    return;
}inline void lca(int x,int y,int u){
    if(d[x]<d[y])swap(x,y);
    while(d[x]!=d[y]){
		if(c[x]==N){c[x]=u;qu.push(x);}
		x=father[x];
	}while(x!=y){
        if(c[x]==N){c[x]=u;qu.push(x);}
        x=father[x];
        if(c[y]==N){c[y]=u;qu.push(y);}
        y=father[y];
    }if(c[y]==N){c[y]=u;qu.push(y);}
    return;
}signed main(){
//	fre(A);
    cin>>n>>m;bool flag=0;
    F(i,1,n-1){
        cin>>q;a[q].push_back(i+1);a[i+1].push_back(q);
		c[i+1]=N;if(q!=i)flag=1;
    }if(flag==1){
        build(1,1);F(i,1,m){cin>>q>>p;b[q].push_back(p);b[p].push_back(q);}
        qu.push(1);
		while(qu.size()){
            int top=qu.front();qu.pop();
            F(i,0,b[top].size()-1){lca(top,b[top][i],c[top]+1);}
            //cout<<qu.size()<<"__11111111111111\n";
        }F(i,1,n){if(c[i]!=N)cout<<c[i]<<" ";else cout<<"-1 ";}
    }else{
        F(i,1,m){cin>>q>>p;if(p<q)swap(q,p);e[q]=(max(e[q],p));}
		F(i,2,e[1])ans[i]=1;
        F(i,2,n)if(ans[i]!=0&&e[i]!=0)for(int j=e[i];j>i;sb(j)){if(ans[j]!=0)break;ans[j]=ans[i]+1;}
        F(i,1,n){
            if(i==1)cout<<"0 ";
            else if(ans[i]==0)cout<<"-1 ";
            else cout<<ans[i]<<" ";
        }
    }return 0;
}

//别人的AC
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[500005],d[500005],x,y,s[500005],ldqm;
vector<int> a[500005],b[500005];
queue<int> q;
int da[500005],ba[500005];
void build(int id,int sd){
    s[id]=sd;
    for(int i=0;i<a[id].size();i++){
        if(a[id][i]!=fa[id]){
            fa[a[id][i]]=id;
            build(a[id][i],sd+1);
        }
    }
    return;
}
void lca(int x,int y,int u){
    if(s[x]<s[y]){
        int t=x;
        x=y;
        y=t;
    }
    while(s[x]!=s[y]){
        if(d[x]==500005){
            d[x]=u;
            q.push(x);
        }
        x=fa[x];
    }
    while(x!=y){
        if(d[x]==500005){
            d[x]=u;
            q.push(x);
        }
        x=fa[x];
        if(d[y]==500005){
            d[y]=u;  
            q.push(y);
        }
        y=fa[y];
    }
    if(d[y]==500005){
        d[y]=u;
        q.push(y);
    }
    return;
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
    cin>>n>>m;
    bool bhyuj=1;
    for(int i=1;i<n;i++){
        cin>>x;
        a[x].push_back(i+1);
        a[i+1].push_back(x);
        d[i+1]=500005;
        if(x!=i)bhyuj=0;
    }
    if(bhyuj==0){
        build(1,1);
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            b[x].push_back(y);
            b[y].push_back(x);
        }
        q.push(1);
        while(q.size()){
            int zdldqm=q.front();
            q.pop();
            for(int i=0;i<b[zdldqm].size();i++){
                lca(zdldqm,b[zdldqm][i],d[zdldqm]+1);
            }
        }
        for(int i=1;i<=n;i++){
            if(d[i]!=500005)cout<<d[i]<<" ";
            else cout<<"-1 ";
        }
    }
    else{
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            if(y<x){
                ldqm=x;
                x=y;
                y=ldqm;
            }
            ba[x]=(max(ba[x],y));
        }
        for(int i=2;i<=ba[1];i++)da[i]=1;
        for(int i=2;i<=n;i++){
            if(da[i]!=0&&ba[i]!=0){
                for(int j=ba[i];j>i;j--){
                    if(da[j]!=0)break;
                    da[j]=da[i]+1;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(i==1)cout<<"0 ";
            else if(da[i]==0)cout<<"-1 ";
            else cout<<da[i]<<" ";
        }
    }
    return 0;
}