CE求调
查看原帖
CE求调
622631
u_lcp楼主2024/6/18 17:52
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,val[maxn];
vector<int> e[maxn];
int sorted[maxn];
int dep[maxn],fa[maxn],top[maxn],siz[maxn],wc[maxn],dfn[maxn],tot;
struct sgt
{
    int ls,rs,val;
}t[maxn<<5];
int lst,kk;
int rt[maxn],cnt;
void build(int &o,int l,int r)
{
    o=++cnt;
    if(l==r)return;
    build(t[o].ls,l,((l+r)>>1));
    build(t[o].rs,((l+r)>>1)+1,r);
}
void change(int &o,int p,int l,int r,int idx)
{
    t[o=++cnt]=t[p],t[o].val++;
    if(l==r)return;
    if(idx<=((l+r)>>1))change(t[o].ls,t[p].ls,l,((l+r)>>1),idx);
    else change(t[o].rs,t[p].rs,((l+r)>>1)+1,r,idx);

}
int query(int u,int v,int anc,int fanc,int l,int r,int k)
{
    if(l==r)return l;
    int x=t[t[u].ls].val+t[t[v].ls].val-t[t[anc].ls].val-t[t[fanc].ls].val;
    if(k<=x)return query(t[u].ls,t[v].ls,t[anc].ls,t[fanc].ls,l,((l+r)>>1),k);
    else return query(t[u].rs,t[v].rs,t[anc].rs,t[fanc].rs,((l+r)>>1)+1,r,k-x);
}
void dfs1(int u)
{
    siz[u]=1;
    for(int v:e[u])
    {
        if(v==fa[u])continue;
        fa[v]=u,dep[v]=dep[u]+1;
        dfs1(v);
        siz[u]+=siz[v],wc[u]=siz[wc[u]]<siz[v]?v:wc[u];
    }
}
void dfs2(int u,int t)
{
    top[u]=t;
    int idx=lower_bound(sorted+1,sorted+kk+1,val[u])-sorted;
    change(rt[dfn[u]=++tot],rt[dfn[fa[u]]],1,kk,idx);
    if(wc[u])
    {
        dfs2(wc[u],t);
        for(int v:e[u])if(v!=wc[u]&&v!=fa[u])dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])y=fa[top[y]];
        else x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void solve(int u,int v,int k)
{
    int anc=lca(u,v);
    int ans=query(rt[dfn[u]],rt[dfn[v]],rt[dfn[anc]],rt[dfn[fa[anc]]],1,kk,k);
    printf("%d\n",sorted[ans]);

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]),sorted[i]=val[i];
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    sort(sorted+1,sorted+n+1);
    kk=unique(sorted+1,sorted+n+1)-sorted-1;
    dep[1]=1;
    dfs1(1),dfs2(1,1);
    for(int i=1,u,v,k;i<=m;i++)scanf("%d%d%d",&u,&v,&k),solve(u,v,k);
    return 0;
}
2024/6/18 17:52
加载中...