题解：P7518 [省选联考 2021 A/B 卷] 宝石

zzzyyyyhhhhh · 2025-02-26 19:01:12 · 个人记录

复杂度 O(q\log n\alpha (c))。

先说一个 \log^2 的，离线所有询问，树链剖分拆出来所有链。开 c 个平衡树，把每个询问塞到对应答案的平衡树中，在每条链上一边走路一边匹配，当前走到点的权值等于 p_i 那么就将第 i-1 棵树合并到第 i 棵树，需要拿出点时所在树的编号即为拿出的点走完这条链的答案。

可以把平衡树换成并查集。

#include<bits/stdc++.h>
using namespace std;
const int N= 2e5+100;
int n,m,c;
int ft[N],dep[N],siz[N],son[N],top[N],lf[N],cnt;
int P[N],pos[N],w[N],t[N];
int f[N*18],tot,k[N*18],to[N*18];
vector<int> a[N];
vector<int> st1[N],st2[N],ed1[N],ed2[N];
int ans[N];
struct st{int id,ad;};
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void dfs(int x,int fa)
{
    ft[x]=fa,siz[x]=1;
    for(auto i:a[x])
    {
        if(i==fa)continue;
        dep[i]=dep[x]+1,dfs(i,x);
        siz[x]+=siz[i];
        if(siz[i]>siz[son[x]])son[x]=i;
    }
}
inline void dfs(int x)
{
    if(!son[x]){lf[++cnt]=x;return;}
    top[son[x]]=top[x];
    dfs(son[x]);
    for(auto i:a[x])if(i!=ft[x]&&i!=son[x])top[i]=i,dfs(i);
}
inline int lca(int x,int y)
{
    while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=ft[top[x]];}
    return dep[x]>dep[y]?y:x;
}
inline void work(int x,int y,int id)
{
    int lc=lca(x,y);
    ed2[y].push_back(id);
    while(top[y]!=top[lc])
    {
        ed2[ft[top[y]]].push_back(id);
        st2[top[y]].push_back(id);
        y=ft[top[y]];
    }
    st2[lc].push_back(id);
    ed1[lc].push_back(id);
    st1[x].push_back(id);
}
inline void uni(int x,int y)
{
    f[t[x]]=find(t[y]),t[x]=++tot,f[tot]=tot,k[t[x]]=x;
}
#define out(X) cerr<<X<<' '<<x<<' '<<i<<'\n';
inline void upp(int x)
{
    int ed=ft[top[x]];
    unordered_set<int> s;
    while(1)
    {
        for(auto i:st1[x])f[++tot]=t[ans[i]],to[i]=tot,s.insert(i);
        if(pos[w[x]])
            uni(pos[w[x]]-1,pos[w[x]]);
        for(auto i:ed1[x])
            ans[i]=k[find(to[i])],s.erase(i);
        x=ft[x];
        if(x==ed)
        {
            for(auto i:s)ans[i]=k[find(to[i])],st1[x].push_back(i);
            return;
        }
    }
}
inline void up(int x)
{
    x=top[x];
    unordered_set<int> s;
    while(1)
    {
        for(auto i:st2[x])f[++tot]=t[ans[i]],to[i]=tot,s.insert(i);
        if(pos[w[x]])
            uni(pos[w[x]]-1,pos[w[x]]);
        for(auto i:ed2[x])
            ans[i]=k[find(to[i])],s.erase(i);
        if(!son[x])return;
        x=son[x];
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>c;
    for(int i=1;i<=c;i++)cin>>P[i],pos[P[i]]=i;
    for(int i=1;i<=n;i++)cin>>w[i];
    int x,y;
    for(int i=1;i<n;i++)cin>>x>>y,a[x].push_back(y),a[y].push_back(x);
    for(int i=0;i<=c;i++)t[i]=++tot,f[tot]=tot,k[tot]=i;
    dfs(1,0),top[1]=1,dfs(1);
    int qq;
    cin>>qq;
    for(int i=1;i<=qq;i++)cin>>x>>y,work(x,y,i);
    sort(lf+1,lf+cnt+1,[](int x,int y){return dep[top[x]]>dep[top[y]];});
    for(int i=1;i<=cnt;i++)upp(lf[i]);
    sort(lf+1,lf+cnt+1,[](int x,int y){return dep[top[x]]<dep[top[y]];});
    for(int i=1;i<=cnt;i++)up(lf[i]);
    for(int i=1;i<=qq;i++)
        cout<<ans[i]<<'\n';
}