巅峰赛#25 T3

本人还没有厉害到随便一写就能写出简单的代码，所以代码较长请耐心观看
首先最简单的我们先建树（t1和t2）以及打出基本的最近公共祖先代码
为防止题解过于笨重这里只展示其中一棵树的关键代码

void dfs1(int u,int f){
	dep1[u]=dep1[f]+1;
    f1[u][0]=f;
    for(auto v:t1[u]){
        if(v!=f)
        	dfs1(v,u);
    }
}

void init(){
    f1[1][0]=f2[1][0]=1;
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f1[i][j]=f1[f1[i][j-1]][j-1];
            f2[i][j]=f2[f2[i][j-1]][j-1];
        }
        
    }
}
int lca1(int u,int v){
    if(v==-1)return u;
    if(dep1[u]<dep1[v]){
        swap(u,v);
    }
    if(dep1[u]!=dep1[v]){
        for(int i=20;i>=0;i--){
            if(dep1[f1[u][i]]>=dep1[v]){
                u=f1[u][i];
            }
        }
    }
    if(u==v)
        return v;
    for(int i=20;i>=0;i--){
        if(f1[u][i]!=f1[v][i]){
            u=f1[u][i];
            v=f1[v][i];
        }
    }
    return f1[u][0];
}	

到这里你已经完成了代码的30%
然后下面是暴力code(40%样例代码可过)

#include<bits/stdc++.h>//注释只是我方便之后发题解，不是AI，我真的没用
using namespace std;
vector<int>t1[200010];//建树
vector<int>t2[200010];
int x[200010];
int vis1[200010],vis2[200010];
int son1[200010],son2[200010];
int dep1[200010],dep2[200010],f1[200010][25],f2[200010][25];
int n,m;
void dfs1(int u,int f){
	dep1[u]=dep1[f]+1;
    f1[u][0]=f;
    for(auto v:t1[u]){
        dfs1(v,u);
        son1[u]+=son1[v];
    }
    if(x[u])
        son1[u]++;
}
void dfs2(int u,int f){
	dep2[u]=dep2[f]+1;
    f2[u][0]=f;
    //cout<<u<<' '<<f2[u][0]<<'\n';
    for(auto v:t2[u]){
        dfs2(v,u);
        son2[u]+=son2[v];
    }
    if(x[u])
        son2[u]++;
}
void init(){
    //cout<<f1[4][0];
    f1[1][0]=f2[1][0]=1;
    //cout<<f1[4][0];
    for(int j=1;j<=20;j++){
        //cout<<f1[4][0];
        for(int i=1;i<=n;i++){
            f1[i][j]=f1[f1[i][j-1]][j-1];
            f2[i][j]=f2[f2[i][j-1]][j-1];
            //cout<<i<<' '<<j<<' '<<f1[i][j]<<endl;
            //cout<<f1[4][0];
        }
        
    }
    //cout<<f1[4][0];
}
int lca1(int u,int v){
    while(dep1[u]<dep1[v]){
        swap(u,v);
    }
    if(dep1[u]!=dep1[v]){
        for(int i=20;i>=0;i--){
            if(dep1[f1[u][i]]>=dep1[v]){
                u=f1[u][i];
            }
        }
    }
    if(u==v)
        return v;
    for(int i=20;i>=0;i--){
        if(f1[u][i]!=f1[v][i]){
            u=f1[u][i];
            v=f1[v][i];
        }
    }
    return f1[u][0];
}	
int lca2(int u,int v){
    while(dep2[u]<dep2[v]){
        swap(u,v);
    }
    if(dep2[u]!=dep2[v]){
        for(int i=20;i>=0;i--){
            if(dep2[f2[u][i]]>=dep2[v]){
                u=f2[u][i];
            }
        }
    }
    if(u==v)
        return v;
    for(int i=20;i>=0;i--){
        if(f2[u][i]!=f2[v][i]){
            u=f2[u][i];
            v=f2[v][i];
        }
    }
    return f2[u][0];
}
int pa(int k,int l){
    int t=l;
    //cout<<t;
	for(int i=1;i<=n;i++){
    	if(x[i]&&i!=k){
            //cout<<i<<' '<<t<<' ';
        	t=lca1(t,i);
            //cout<<t<<'\n';
        }
    }
    return t;
}
int pb(int k,int l){
    int t=l;
    //cout<<k<<' ';
	for(int i=1;i<=n;i++){
        //cout<<x[i]<<' ';
    	if(x[i]&&i!=k){
            //cout<<i<<' '<<t<<' ';
        	t=lca2(i,t);
            //cout<<t<<'\n';
        }
    }
    return t;
}
int main(){
    cin>>n>>m;
	int a[200010],b[200010],p[200010];//记录权值
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    for(int i=2;i<=n;i++){
    	int u;
        cin>>u;
        t1[u].push_back(i);
    }
    for(int i=1;i<=n;i++){
    	cin>>b[i];
    }
    for(int i=2;i<=n;i++){
    	int u;
        cin>>u;
        t2[u].push_back(i);
        //cout<<u<<' '<<i<<endl;
    }
	int k;
    for(int i=1;i<=m;i++){
        cin>>k;
        p[i]=k;
        x[k]=1;
    }
    dfs1(1,0);
    dfs2(1,0);
    
    init();
    //cout<<lca1(3,5);
    //cout<<f1[4][0];
    int al=k,bl=k;
    //cout<<lca2(1,2);
    for(int i=1;i<=n;i++){
    	if(x[i]){
        	al=lca1(al,i);
            bl=lca2(bl,i);
        }
    }
    
    //cout<<k;
    for(int i=1;i<=m;i++){
        	int k1=a[pa(p[i],k)],k2=b[pb(p[i],k)];
            //cout<<k1<<' '<<k2<<' ';
        	if(k1>k2)
                cout<<"YES";
            else
                cout<<"NO";
            cout<<'\n';
            k=p[i];
    }
    //cout<<son1[al]<<' '<<son2[bl];
}

接下来就到了我们的优化时间
我们现在可以发现查询时的复杂度是O(m·n·log n)
包超时的啊牢弟
这个时候我们就要动动双手画几棵二叉树
（本人画工太差，也没有合适软件，看到这里的可以推荐一个实用的吗？）

通过代表我们显然可以发现当全体的最近公共祖先只会在一下几个点删除时改变
前置条件：每个最近公共祖先一定会有大于等于两个含有标记节点的子树
1.含有两棵有标记的子树，且子树标记数为1时则会影响最近公共祖先
2.当标记节点就是全体最近公共祖先时，会改变

经过以上分析，我们只要找出所有符合以上条件的子节点，并对其进行一次求解最近公共祖先即可
预处理时间复杂度理论不会超过(nlogn)
感谢午枫没有给刁钻数据

AC code:

#include<bits/stdc++.h>
using namespace std;
vector<int>t1[200010];//建树
vector<int>t2[200010];
int x[200010],v1[200010],v2[200010];
int vis1[200010],vis2[200010];
int a[200010],b[200010],p[200010];
int dep1[200010],dep2[200010],f1[200010][25],f2[200010][25];
int n,m;
void dfs1(int u,int f){
	dep1[u]=dep1[f]+1;
    f1[u][0]=f;
    if(x[u])
        vis1[u]++;
    for(auto v:t1[u]){
        if(v!=f)
        	dfs1(v,u);
    }
    vis1[f]+=vis1[u];
}
void dfs2(int u,int f){
	dep2[u]=dep2[f]+1;
    f2[u][0]=f;
    if(x[u])
        vis2[u]++;
    for(auto v:t2[u]){
        if(v!=f)
        	dfs2(v,u);
    }
    vis2[f]+=vis2[u];
}
void init(){
    f1[1][0]=f2[1][0]=1;
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f1[i][j]=f1[f1[i][j-1]][j-1];
            f2[i][j]=f2[f2[i][j-1]][j-1];
        }
        
    }
}
int lca1(int u,int v){
    if(v==-1)return u;
    if(dep1[u]<dep1[v]){
        swap(u,v);
    }
    if(dep1[u]!=dep1[v]){
        for(int i=20;i>=0;i--){
            if(dep1[f1[u][i]]>=dep1[v]){
                u=f1[u][i];
            }
        }
    }
    if(u==v)
        return v;
    for(int i=20;i>=0;i--){
        if(f1[u][i]!=f1[v][i]){
            u=f1[u][i];
            v=f1[v][i];
        }
    }
    return f1[u][0];
}	
int lca2(int u,int v){
    if(v==-1)return u;
    if(dep2[u]<dep2[v]){
        swap(u,v);
    }
    if(dep2[u]!=dep2[v]){
        for(int i=20;i>=0;i--){
            if(dep2[f2[u][i]]>=dep2[v]){
                u=f2[u][i];
            }
        }
    }
    //cout<<u<<' '<<v<<'\n';
    if(u==v)
        return v;
    for(int i=20;i>=0;i--){
        if(f2[u][i]!=f2[v][i]){
            u=f2[u][i];
            v=f2[v][i];
        }
    }
    return f2[u][0];
}
int dfss1(int u){
	if(x[u])
        return u;
    for(auto v:t1[u]){
    	if(vis1[v])
            return dfss1(v);
    }
    return 0;
}
int dfss2(int u){
    if(x[u])
        return u;
    for(auto v:t2[u]){
    	if(vis2[v])
            return dfss2(v);
    }
    return u;
}//dfss是为了寻找符合条件节点
int pa(int k){
    int t=-1;
    for(int i=1;i<=m;i++){
        
    	if(p[i]!=k)t=lca1(p[i],t);
        //cout<<t;
        if(t==1)return t;
    }
    //cout<<t;
    if(t==-1)return 0;
    return t;
}
int pb(int k){
    int t=-1;
	for(int i=1;i<=m;i++){
    	if(p[i]!=k)t=lca2(p[i],t);
        //cout<<t;
        if(t==1)return t;
    }
    if(t==-1)return 0; 
    return t;
}//pa,pb是为了求解符合条件会变化的最近公共祖先
int main(){
    cin>>n>>m;
	
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    for(int i=2;i<=n;i++){
    	int u;
        cin>>u;
        t1[u].push_back(i);
    }
    for(int i=1;i<=n;i++){
    	cin>>b[i];
    }
    for(int i=2;i<=n;i++){
    	int u;
        cin>>u;
        t2[u].push_back(i);
    }
	int k;
    for(int i=1;i<=m;i++){
        cin>>k;
        p[i]=k;
        x[k]=1;
    }
    dfs1(1,0);
    dfs2(1,0);
    init();
    //cout<<lca2(3,4);
    int al=p[1],bl=p[1];//保存最近公共祖先
    for(int i=2;i<=m;i++){
    	al=lca1(p[i],al);
        bl=lca2(p[i],bl);
    }
    //cout<<vis1[i]<<' '<<vis2[i]<<'\n';
 	//简单来说我们的目标是把时间优化到O（1） 
    //通过打表可得每棵树最多只会有一个节点改变祖先
    //（其实不止：发题解的时候发现此处注释有误）
    //cout<<a[al]<<' '<<bl<<'\n';
    int ak=-1,bk=-1;
    
    for(auto v:t1[al]){
        //cout<<vis1[v];
    	if(vis1[v]==1){
            ak=v;
            v1[dfss1(ak)]=1;
        }
    }
    for(auto v:t2[bl]){
        //cout<<vis
    	if(vis2[v]==1){
            bk=v;
            v2[dfss2(bk)]=v;
        
        }
    }
    //cout<<ak<<' '<<bk;
    int ak2=-1;
    int bk2=-1;
    if(x[al])ak2=al;
    if(x[bl])bk2=bl;
    //cout<<ak1<<' '<<bk1<<'\n';
    //cout<<al<<' '<<bl;
    for(int i=1;i<=m;i++){
        int l=al,r=bl;
    	if(v2[p[i]]||bk2==p[i]){
        	r=pb(p[i]);
            //cout<<r;
            //cout<<'\\';
        }
        if(v1[p[i]]||ak2==p[i]){
        	l=pa(p[i]);
            //cout<<'\\';
        }
        //cout<<a[l]<<' ';
        //cout<<l<<' '<<r<<'\n';
        if(a[l]>b[r])
            cout<<"YES";
        else
            cout<<"NO";
        cout<<'\n';
    }
}

//代码较长，感谢耐心观看