小蓝的疑问【算法赛】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int w[N];//w

vector<int> g[N];
vector<pair<int,int> >qr[N];
int ans[N];
map<int,int>cnt[N];//第一维深度，第二维点权，第三维记录是否存在
int son[N],sz[N];//重儿子
int L[N],R[N],dfn,id[N],a[N],dep[N];
void dfs1(int u,int fa){//求重儿子
    son[u]=1;
    L[u]=++dfn;//dfn序
    id[dfn]=u;
    a[dfn]=w[u];
    dep[u]=dep[fa]+1;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        son[u]+=son[v];
        if(son[v]>son[sz[u]]) sz[u]=v; 
    }
    R[u]=dfn;
}

void dfs2(int u,int fa,bool op){//启发式合并
    for(int v:g[u]){
        if(v==fa||v==sz[u]) continue;
        dfs2(v,u,false);
    }
    if(sz[u]){
        dfs2(sz[u],u,true);
    }
    for(int v:g[u]){
        if(v==fa||v==sz[u]) continue;
        for(int i=L[v];i<=R[v];i++){
            cnt[dep[id[i]]][a[i]]++;
        }
    }
    cnt[dep[u]][w[u]]++;
    for(auto v:qr[u]){//离线查询
        int idd=v.second,k=v.first+dep[u];
        if(cnt[k].size()){
            ans[idd]=(*cnt[k].rbegin()).first;//反向为大
        }
    }
    if(!op){//不是重儿子
        for(int i=L[u];i<=R[u];i++){
           cnt[dep[id[i]]].erase(a[i]);//轻儿子的部分删掉
        }
    }

}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=q;i++){
        int x,k;
        cin>>x>>k;
        qr[x].push_back({k,i});
    }
    dfs1(1,0);
    dfs2(1,0,false);
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}