ADASALES - Batman

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[100004];
vector<vector<int>>g;
vector<int>dv;
bitset<100004>vis;
set<pair<ll,int>>s[100004];
ll ans[100004];
void dfs(int x){
    vis[x]=1;
    dv.push_back(x);
    for(int u:g[x])if(!vis[u]){
        dfs(u);
        if(s[u].size()){
            s[x].insert({s[u].rbegin()->first+max(p[u]-p[x],0),u});
            if(s[x].size()>2)s[x].erase(s[x].begin());
        }
        else if(p[u]-p[x]>0){
            s[x].insert({p[u]-p[x],u});
            if(s[x].size()>2)s[x].erase(s[x].begin());
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    int n,q,i,x,y;
    set<pair<ll,int>>::reverse_iterator it,eit;
    cin>>n>>q;
    for(i=0;i<n;++i)cin>>p[i];
    g.assign(n,dv);
    for(i=1;i<n;++i){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0);
    if(s[0].empty())s[0].insert({0,0});
    for(i=1;i<n;++i){
        x=dv[i];
        for(int u:g[x]){
            eit=s[u].rend();
            for(it=s[u].rbegin();it!=eit;++it)if(it->second!=x&&it->first+max(p[u]-p[x],0)){
                s[x].insert({it->first+max(p[u]-p[x],0),u});
                if(s[x].size()>2)s[x].erase(s[x].begin());
                break;
            }
            if(it==eit&&p[u]-p[x]>0){
                s[x].insert({p[u]-p[x],u});
                if(s[x].size()>2)s[x].erase(s[x].begin());
            }
        }
        if(s[x].empty())s[x].insert({0,x});
    }
    for(i=0;i<n;++i)ans[i]=s[i].rbegin()->first;
    while(q--){
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}