题解 P7518【[省选联考 2021 A/B 卷] 宝石】
whiteqwq
·
·
题解
P7518 [省选联考 2021 A/B 卷] 宝石解题报告：
更好的阅读体验
题意
给定一颗n个点的带点权的树，以及一个长度为c的匹配序列，（点权与序列的值域为[1,m]），q次询问，每次询问x到y的有向路径与匹配序列匹配的最长前缀的长度。
## 分析
考场写了一个5k的树分块$O((n+q+m\alpha(n))\sqrt{n})$的做法，然后被卡常卡成$35pts$就很离谱。
>
（该部分可略过）
在树上撒$\sqrt{n}$个关键点，每个点与其祖先里的关键点距离为$\sqrt{n}$，然后发现可以把询问的路径分成$4$个散块和$2$个整块，散块暴力跳（记得把$lca$到另一端的路径反向，我因为反向调了一个多小时），整块可以预处理第$i$个关键点跳到祖先关键点这一条链，从位置$j$开始匹配能匹配到哪里，不难发现（我想了十几分钟）可以用并查集维护所有位置同时进行匹配，同样还要反过来做一遍。
具体地，可以把整块对应的链上权值序列当成一个普通的序列，与长度为m的串进行匹配，然后对于每个位置可以维护它在匹配的过程中到了哪一个位置，不难发现把相同的位置在匹配的过程中会不断合并，那么直接上并查集就好了。
然后发现$O(n\log n+q\log n\log m)$的树上倍增好想好写的一批。
首先进行一次转化，把点权转化为在序列中的位置，这样好做一些。
考虑预处理$x$向上跳第一个点权为$c$的点的位置，这是一个经典问题，在树上用主席树完成就好了，时空复杂度均为$O(n\log m)$。
然后再按照树上倍增的套路预处理一个$inc_{x,k}$表示$x$向上跳，从当前点权$w_x$匹配到$w_x+2^k$的位置，以及$dec_{x,k}$表示$x$向上跳，从当前点权$w_x$反向匹配到$w_x-2^k$的位置。我们首先用主席树帮忙处理出$inc_{x,0}$与$dec_{x,0}$，然后直接合并就好了。
对于询问$(x,y)$，设$z=lca(x,y)$，考虑让$x$跳到第一个点权为$1$的点开始匹配（需要特判一下跳出$x\rightarrow z$这一条链的情况），然后用树上倍增暴力跳$inc$数组直到跳出$x\rightarrow z$这一条链。
之后，我们发现$y$不能进行类似的操作，因为我们不知道结尾的点权为多少，不难发现答案具有可二分性，直接二分最后的位置，然后按照上面的方法跳$dec$就好了。
时间复杂度：$O(n\log n+q\log n\log m)$。
## 代码
常数似乎很大。
```
#include<stdio.h>
const int maxm=50005,maxn=200005,maxe=maxn<<1,maxk=25;
int n,m,c,e,q,tot;
int p[maxm],w[maxn],start[maxn],to[maxe],then[maxe],fore[maxn][maxk],dep[maxn],pos[maxm];
int lc[maxn*maxk],rc[maxn*maxk],res[maxn*maxk],rt[maxn],inc[maxn][maxk],dec[maxn][maxk];
inline void add(int x,int y){
then[++e]=start[x],start[x]=e,to[e]=y;
}
void build(int l,int r,int &now){
if(now==0)
now=++tot;
if(l==r){
res[now]=-1;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lc[now]),build(mid+1,r,rc[now]);
}
inline int newnode(int x){
tot++,lc[tot]=lc[x],rc[tot]=rc[x],res[tot]=res[x];
return tot;
}
void update(int l,int r,int &now,int pos,int v){
now=newnode(now);
if(l==r){
res[now]=v;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid)
update(l,mid,lc[now],pos,v);
else update(mid+1,r,rc[now],pos,v);
}
int query(int l,int r,int now,int pos){
if(l==r)
return res[now];
int mid=(l+r)>>1;
if(pos<=mid)
return query(l,mid,lc[now],pos);
return query(mid+1,r,rc[now],pos);
}
void dfs(int x,int last){
dep[x]=dep[last]+1,fore[x][0]=last,rt[x]=rt[last];
if(w[x]!=-1)
update(1,c,rt[x],w[x],x);
inc[x][0]=(w[x]==-1||w[x]==c)? -1:query(1,c,rt[x],w[x]+1);
dec[x][0]=(w[x]==-1||w[x]==1)? -1:query(1,c,rt[x],w[x]-1);
for(int i=1;i<=20;i++){
fore[x][i]=fore[fore[x][i-1]][i-1];
inc[x][i]=inc[x][i-1]==-1? -1:inc[inc[x][i-1]][i-1];
dec[x][i]=dec[x][i-1]==-1? -1:dec[dec[x][i-1]][i-1];
}
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(y==last)
continue;
dfs(y,x);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])
a+=b,b=a-b,a-=b;
for(int i=20;i>=0;i--)
if(dep[fore[a][i]]>=dep[b])
a=fore[a][i];
if(a==b)
return a;
for(int i=20;i>=0;i--)
if(fore[a][i]!=fore[b][i])
a=fore[a][i],b=fore[b][i];
return fore[a][0];
}
int check(int x,int z,int now,int goal){
x=query(1,c,rt[x],goal);
if(x==-1||dep[x]<dep[z])
return 0;
for(int i=20;i>=0;i--)
if(dec[x][i]!=-1&&dep[dec[x][i]]>dep[z])
x=dec[x][i];
return w[x]<=now;
}
int main(){
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=m;i++)
pos[i]=-1;
for(int i=1;i<=c;i++)
scanf("%d",&p[i]),pos[p[i]]=i;
for(int i=1;i<=n;i++)
scanf("%d",&w[i]),w[i]=pos[w[i]];
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
build(1,c,rt[0]),dfs(1,0);
scanf("%d",&q);
while(q--){
int x,y,z,res=0;
scanf("%d%d",&x,&y),z=lca(x,y);
x=query(1,c,rt[x],1);
if(x!=-1&&dep[x]>=dep[z]){
for(int i=20;i>=0;i--)
if(inc[x][i]!=-1&&dep[inc[x][i]]>=dep[z])
x=inc[x][i];
res=w[x];
}
int L=res,R=c+1;
while(L+1<R){
int mid=(L+R)>>1;
if(check(y,z,res+1,mid))
L=mid;
else R=mid;
}
printf("%d\n",L);
}
return 0;
}
```
省选联考A卷全部题解可见：[2021省选联考A卷解题报告](https://zybuluo.com/xiaoziyao/note/1791034)