联合省选 2021 宝石 题解

看到好像没什么人是和我思路类似的单 \log 做法，我就来水一篇 blog 了。

对于一条询问路径 s_i\rightarrow t_i 拆成 s_i\rightarrow x_i 和 y_i\rightarrow t_i，其中 y_i 是 s_i,t_i 的 LCA，x_i 是 y_i 的儿子。

对于 s_i\rightarrow x_i 的部分，我们直接处理出这一段最多可以获得多少宝石，并把下一个宝石的种类记为 c_i，然后把二元组 (c_i,i) 挂到节点 y_i 上，并在节点 t_i 上挂一个结束标记 i。

这个部分可以用树上倍增进行处理。

现在只需要对树进行一遍 dfs，并对每个宝石的种类 i 维护一个容器 d_i，支持：

1. 进入点 k 时，对于挂在 k 上的所有二元组 (i,x)，把 x 插入容器 d_i。
2. 令点 k 上的宝石种类 w 在宝石序列中的后继为 r，则把 d_{w} 合并到 d_{r} 中。
3. 对于挂在 k 上的所有结束标记 x，查询 x 所在的容器编号。
4. 退出点 k 时，撤销进入点 k 时进行的操作（包括插入与合并）。

我们发现用带撤销并查集可以很好的实现这个容器。

于是就做完了，时间复杂度 O((n+q)\log n)。

upd: 2023.10.25 bug fixed.

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N=500000,C=21;

int Ri(){
  int x=0,y=1;
  char c=getchar();
  for (;c<'0'||c>'9';c=getchar()) if (c=='-') y=-1;
  for (;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';
  return x*y;
}

int n,m,sk,a[N+9],pre[N+9],suf[N+9],pos[N+9];
struct side{
  int y,next;
}e[N+9];
int lin[N+9],cs;

void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}
void Ins2(int x,int y){Ins(x,y);Ins(y,x);}

int fa[N+9],son[N+9],dep[N+9],siz[N+9],top[N+9];
int fir,up1[N+9],up[N+9][C],now[N+9];

void Dfs_ord0(int k,int fat){
  if (now[suf[a[k]]]) up[k][0]=now[suf[a[k]]];
  for (int i=1;i<C;++i) up[k][i]=up[up[k][i-1]][i-1];
  int t=now[a[k]];
  now[a[k]]=k;
  if (now[fir]) up1[k]=now[fir];
  fa[k]=fat;
  dep[k]=dep[fat]+1;
  siz[k]=1;
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fat){
      Dfs_ord0(e[i].y,k);
      siz[k]+=siz[e[i].y];
      if (siz[e[i].y]>siz[son[k]]) son[k]=e[i].y;
    }
  now[a[k]]=t;
}

void Dfs_ord1(int k,int t){
  top[k]=t;
  if (son[k]) Dfs_ord1(son[k],t);
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fa[k]&&e[i].y^son[k]) Dfs_ord1(e[i].y,e[i].y);
}

int Query_lca(int x,int y){
  for (;top[x]^top[y];x=fa[top[x]])
    if (dep[top[x]]<dep[top[y]]) swap(x,y);
  return dep[x]<dep[y]?x:y;
}

int cq,ans[N+9];
vector<int>qc[N+9],qid[N+9],q[N+9];

void into(){
  n=Ri();m=Ri();sk=Ri();
  for (int i=1;i<=sk;++i) a[i]=Ri();
  fir=a[1];
  for (int i=1;i<=sk;++i){
    pre[a[i]]=a[i-1];
    suf[a[i]]=a[i+1];
    pos[a[i]]=i;
  }
  for (int i=1;i<=n;++i) a[i]=Ri();
  for (int i=1;i<n;++i){
    int x,y;
    x=Ri();y=Ri();
    Ins2(x,y);
  }
  Dfs_ord0(1,0);
  Dfs_ord1(1,1);
  cq=Ri();
  for (int i=1;i<=cq;++i){
    int x,y,z;
    x=Ri();y=Ri();
    z=Query_lca(x,y);
    if (dep[up1[x]]<=dep[z]){
      qc[z].push_back(fir);
      qid[z].push_back(i);
      q[y].push_back(i);
    }else{
      int t=up1[x];
      for (int j=C-1;j>=0;--j)
        if (dep[up[t][j]]>dep[z]) t=up[t][j];
      t=a[t];
      if (suf[t]){
        qc[z].push_back(suf[t]);
        qid[z].push_back(i);
        q[y].push_back(i);
      }else ans[i]=sk;
      // }else ans[i]=m;
    }
  }
}

int uni[N+9],sz[N+9],col[N+9],rot[N+9];

int Query_uni(int k){return k==uni[k]?k:Query_uni(uni[k]);}

void Dfs_ans(int k){
  for (int vs=qc[k].size(),i=0;i<vs;++i){
    int c=qc[k][i],t=qid[k][i];
    uni[t]=t;sz[t]=1;col[t]=c;
    rot[c]?(uni[t]=rot[c],++sz[rot[c]]):rot[c]=t;
  }
  int x=rot[a[k]];
  rot[a[k]]=0;
  int c=suf[a[k]],y=rot[c];
  if (x){
    if (!y) rot[c]=x,col[x]=c;
    else if (sz[x]<sz[y]){
      uni[x]=y;
      sz[y]+=sz[x];
    }else{
      uni[y]=rot[c]=x;
      sz[x]+=sz[y];
      col[x]=c;
    }
  }
  for (int vs=q[k].size(),i=0;i<vs;++i){
    int t=col[Query_uni(q[k][i])];
    ans[q[k][i]]=t?pos[t]-1:sk;
  }
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fa[k]) Dfs_ans(e[i].y);
  if (x){
    if (!y) rot[c]=0,col[x]=a[k];
    else if (rot[c]==y){
      uni[x]=x;
      sz[y]-=sz[x];
    }else{
      uni[y]=rot[c]=y;
      sz[x]-=sz[y];
      col[x]=a[k];
    }
  }
  rot[a[k]]=x;
  for (int vs=qc[k].size(),i=0;i<vs;++i){
    int c=qc[k][i],t=qid[k][i];
    rot[c]==t?rot[c]=0:--sz[uni[t]];
  }
}

void work(){
  Dfs_ans(1);
}

void outo(){
  for (int i=1;i<=cq;++i)
    printf("%d\n",ans[i]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}