联合省选 2021 宝石 题解
hezlik
2021-04-15 21:13:33
看到好像没什么人是和我思路类似的单 $\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.
代码如下：
```cpp
#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;
}
```