神秘 RE 求助

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a),E##i=(b);i<=E##i;i++)
#define REV(i,a,b) for(int i=(a),E##i=(b);i>=E##i;i--)
#define CLOSE_TIE ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define psbk push_back
#define endl '\n'
#define int unsigned int
template <typename T>
void _outval(string s,int p,const T &t) {cout<<s.substr(p,s.length()-p)<<'='<<t<<endl; }
template <typename T, typename... Args>
void _outval(string s,int p,const T &t,const Args &...rest){
    string n="";
    while(s[p]!=',') n+=s[p++];
    cout<<n<<'='<<t<<", ";
    _outval(s,p+1,rest...);
}
#define outval(...) _outval(#__VA_ARGS__,0,__VA_ARGS__)
#define outarr(a,be,ed)\
{cout<<(#a)<<": ";\
FOR(iiii,be,ed)cout<<'['<<iiii<<"]="<<a[iiii]<<", "; cout<<endl;}
constexpr int N=5e5+5;
int n,m,k,a[N],u[N],ans[N];
int dfn[N],id[N],fa[N],dep[N];
int buf[N*20],*now=buf,*b[N<<2],stk[N<<1],bk1[N];
int nd[N<<1],len;
struct Qu{int l,r,u,id;}q[N];
vector<int> e[N],g[N],bk2[N];
void dfs1(int u){
    dep[u]=dep[fa[u]]+1,id[dfn[u]=++dfn[0]]=u;
    for(int v:e[u])
        if(v!=fa[u]) fa[v]=u,dfs1(v);
}
//dfs 序求 lca
struct ST{
    int st[20][N];
    void init(){
        FOR(i,1,n) st[0][i]=id[i];
        FOR(i,1,__lg(n))
            FOR(j,1,n-(1<<i)+1){
                if(dep[st[i-1][j]]<dep[st[i-1][j+(1<<(i-1))]]) st[i][j]=st[i-1][j];
                else st[i][j]=st[i-1][j+(1<<(i-1))];
            }
    }
    inline int lca(int u,int v){
        if(u==v) return u;
        if(dfn[u]>dfn[v]) swap(u,v);
        int l=dfn[u]+1,r=dfn[v],lgl=__lg(r-l+1);
        return fa[dep[st[lgl][l]]<dep[st[lgl][r-(1<<lgl)+1]]?st[lgl][l]:st[lgl][r-(1<<lgl)+1]];
    }
}st;
inline void addEdge(int u,int v){
    dep[u]<dep[v]?g[u].psbk(v):g[v].psbk(u);
}
inline void dfs2(int u){
    for(int v:g[u]) dfs2(v),bk1[u]+=bk1[v];
}
inline void dfs3(int u,int mx){
    if(!bk2[u].empty()){
        int nmx=max(mx,u*(bool)(bk1[u]));
        for(int i:bk2[u]) ans[i]=max(ans[i],nmx);
        bk2[u].clear();
    }
    for(int v:g[u]) dfs3(v,(bk1[u]-bk1[v]?max(mx,u):mx));
    bk1[u]=0;
}
struct SGT{
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    #define mid ((l+r)>>1)
    vector<int> t[N<<2];
    inline void update(int p,int l,int r,int x,int y,int id){
        if(x<=l&&r<=y) return t[p].psbk(id),void();
        if(x<=mid) update(ls(p),l,mid,x,y,id);
        if(y>mid) update(rs(p),mid+1,r,x,y,id);
    }
    inline void solve(int p,int l,int r){
        b[p]=now,now+=r-l+2;
        if(l==r){
            b[p][1]=a[l];
        }else{
            //归并
            solve(ls(p),l,mid),solve(rs(p),mid+1,r);
            int i,j,k;
            for(i=1,j=1,k=1;i<=mid-l+1&&j<=r-mid;k++){
                if(dfn[b[ls(p)][i]]<dfn[b[rs(p)][j]]) b[p][k]=b[ls(p)][i],++i;
                else b[p][k]=b[rs(p)][j],++j;
            }
            while(i<=mid-l+1) b[p][k]=b[ls(p)][i],++k,++i;
            while(j<=r-mid) b[p][k]=b[rs(p)][j],++k,++j;
        }
        //小数据暴力
        if(r-l+1<=32){
            FOR(i,l,r) for(int j:t[p]) ans[j]=max(ans[j],st.lca(u[j],a[i]));
            return;
        }
        FOR(i,l,r) bk1[a[i]]=1;
        for(int i:t[p]) bk2[u[i]].psbk(i);
        //归并
        len=0; int i,j;
        for(i=1,j=0;i<=r-l+1&&j<t[p].size();){
            if(dfn[b[p][i]]<dfn[u[t[p][j]]]) nd[++len]=b[p][i],++i;
            else nd[++len]=u[t[p][j]],++j;
        }
        while(i<=r-l+1) nd[++len]=b[p][i],++i;
        while(j<t[p].size()) nd[++len]=u[t[p][j]],++j;
        //单调栈建虚树
        int top=1; stk[top]=1; g[1].clear();
        FOR(i,1,len){
            if(nd[i]==1||(i&&nd[i]==nd[i-1])) continue;
            int l=st.lca(nd[i],stk[top]);
            if(l!=stk[top]){
                while(dfn[l]<dfn[stk[top-1]]) addEdge(stk[top-1],stk[top]),--top;
                if(dfn[l]>dfn[stk[top-1]]) g[l].clear(),addEdge(stk[top],l),stk[top]=l;
                else addEdge(l,stk[top]),--top;
            }
            g[nd[i]].clear(),stk[++top]=nd[i];
        }
        FOR(i,1,top-1) addEdge(stk[i],stk[i+1]);
        dfs2(1); dfs3(1,0);
    }
}t;
inline int read(){
    char c=getchar();
    int f=1,res=0;
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=getchar();
    }
    res*=f;
    return res;
}
signed main(){
    CLOSE_TIE
    n=read(),m=read(),k=read();
    FOR(i,2,n){
        int u=read(),v=read();
        e[u].psbk(v),e[v].psbk(u);
    }
    FOR(i,1,m) a[i]=read();
    FOR(i,1,k){q[i].l=read(),q[i].r=read(),q[i].u=read(); u[q[i].id=i]=q[i].u;}

    dfs1(1); st.init();
    sort(q+1,q+k+1,[&](Qu a,Qu b){return dfn[a.u]<dfn[b.u];});
    FOR(i,1,k) t.update(1,1,m,q[i].l,q[i].r,q[i].id);
    t.solve(1,1,m);
    FOR(i,1,k) cout<<ans[i]<<endl;
    return 0;
}