题解：P7518 [省选联考 2021 A/B 卷] 宝石
Ff472130
·
·
题解
P7518 [省选联考 2021 A/B 卷] 宝石
题意
给定一棵树，每个点 u 有种类为 W_u 的宝石，保证 W_u\in [1,m]。你有一个收集器，至多收集 c 颗宝石，并且收集顺序必须为给定的一个序列 P，保证 P 内元素互不相同，每次询问给定树上的一条路径 s \rightarrow t，求你在这条路径上最多收集多少颗宝石。
##### solution
模拟赛题目，考场上看到链部分分的分治，想到用点分治但是死活写不出来，思路很混乱，所以清晰的思路在考场上确实很重要。
这题可以用倍增和二分做到 $O(n\log^2n)$，实现方法与下面的点分治类似，这里不多介绍了。
首先对于 $W$ 做一个映射，令 $W_u$ 为原本 $W_u$ 在 $P$ 中的下标，那么对于新的 $W$，我们收集顺序就变成了 $1,2,3\cdots c$。
将所有询问离线下来，考虑点分治，每次解决跨越分治中心的询问。
首先我们要考虑如何提取出所有跨过分治中心的询问，一个简单的方法就是对所有子树进行染成不同颜色，若询问两个端点颜色不同，那么这个询问是跨过分治中心的，否则将他拿出来，放到对应的子树中处理。
令当前分治中心为 $o$，对于所有询问拆成 $s\rightarrow o$ 和 $o\rightarrow t$ 两部分。
先考虑如何解决 $s\rightarrow o$ 的部分。我们令 $mx_u$ 表示若能拿点 $u$ 的宝石，最多能拿多少个宝石，令 $lst_k$ 表示上一个最近的权值为 $k$ 的节点编号，那么若 $lst_{W_u+1}$ 为 $0$，即 $u\rightarrow o$ 路径上不存在权值为 $W_u+1$ 的节点，则 $mx_u=W_u$，否则 $mx_u=mx_{lst_{W_u+1}}$ 即拿完 $u$ 上的宝石再找到 $W_u+1$ 的位置继续拿宝石，对于 $u\rightarrow o$ 的路径上最多能拿的宝石数量即为所有路径上 $W_v=1$ 的节点 $v$，$mx_v$ 的最大值。
我们考虑如何在 dfs 的过程中动态维护这个东西，遍历到一个点 $u$，那么如上更新 $mx_u$，将 $lst_{W_u}$ 设为 $u$，若 $W_u=1$ 则将答案取 $\max$，遍历完当前节点还要将 $lst_{W_u}$ 还原为原本状态，实际实现可以记录原本 $lst_{W_u}$ 的值，遍历完后修改回来即可。
接下来考虑怎么解决 $o\rightarrow t$ 上的部分。我们先把询问对应 $s\rightarrow o$ 上得到的答案和编号挂在对应的 $t$ 上，在 dfs 到节点 $t$ 的处理这个询问。
我们反着考虑，$o\rightarrow t$ 上选一段递增的序列相当于 $t\rightarrow o$ 选一段递减的序列，再考虑能不能与 $s\rightarrow o$ 的接上，在能接上的前提下使递减序列的开头最大。
设 $mn_u$ 为拿了节点 $u$ 上的宝石后 $u\rightarrow o$ 最低能拿到的宝石权值，转移和上面的类似，令 $lst_k$ 表示上一个最近的权值为 $k$ 的节点编号，那么若 $lst_{W_u-1}$ 为 $0$，则 $mn_u=W_u$，否则 $mn_u=mn_{lst_{W_u-1}}$，用和上面一样的方法维护。
答案显然具有单调性，二分答案后判断能不能接上即可，具体的，令 $s\rightarrow o$ 答案为 $x$，权值 $k$ 可以接上当且仅当 $mn_{lst_k}\ge x+1$，注意二分左边界为 $x+1$。
实现时要注意分治中心不要算重，还有特判起点终点在分治中心上的情况，这样就解决了这道比较神秘的点分治题目。
时间复杂度 $O(n\log n+q(\log n+\log c))$，卡卡常就跑到了[最优解](https://www.luogu.com.cn/record/261863046)。
总的来说，虽然倍增比较好想好做，但这确是一道不错的点分治题目。下面是没有卡常的代码。
:::info[code]
```cpp
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
const int N=2e5+10;
const int inf=1e9+10;
inline void read(int &x) {
x=0;
char ch=getchar();
while (ch<48) ch=getchar();
while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
struct Ctrl_Z_Array {
int v[N],st1[N],st2[N],top;
inline int operator [] (const int &x)const {return v[x];}
inline void update(int x,int k) {top++;st1[top]=x;st2[top]=v[x];v[x]=k;}
inline void remove() {int x=st1[top],k=st2[top];top--;v[x]=k;}
}lst;
int n,m,C_z,qsum;
int c_mp[N],w[N],ans[N];
vector<int> e[N];
int siz[N],wgh[N];
bool del[N];
int rt,sum_siz;
inline void get_rt(int now,int fa) {
siz[now]=1;wgh[now]=0;
for (int v:e[now]) {
if (del[v]||v==fa) continue;
get_rt(v,now);
siz[now]+=siz[v];
wgh[now]=max(wgh[now],siz[v]);
}
wgh[now]=max(wgh[now],sum_siz-siz[now]);
if (wgh[now]<wgh[rt]) rt=now;
}
vector<int> pt;
int col_tot;
int col[N],col_s[N];
int mx_res[N],mx_to[N],mn_to[N];
struct ques{int u,v,id;};
vector<ques> qnxt[N];
struct v_ques{vector<ques>qs;int v;};
struct res_v{int res,id;};
vector<res_v> rs[N];
inline void get_color(int now,int fa,int c) {
col[now]=c;
pt.push_back(now);
for (int v:e[now]) if (v!=fa&&!del[v]) get_color(v,now,c);
}
inline void c_res(int now,int fa,int mx) {
if (w[now]!=-1) {
if (!lst[w[now]+1]) mx_to[now]=w[now];
else mx_to[now]=mx_to[lst[w[now]+1]];
lst.update(w[now],now);
if (w[now]==1) mx=max(mx,mx_to[now]);
}
mx_res[now]=mx;
for (int v:e[now]) if (v!=fa&&!del[v]) c_res(v,now,mx);
if (w[now]!=-1) lst.remove();
}
inline void work(res_v tmp) {
int l=tmp.res+1,r=C_z,res=tmp.res;
while (l<=r) {
int mid=l+r>>1;
if (lst[mid]&&mn_to[lst[mid]]<=tmp.res+1) res=mid,l=mid+1;
else r=mid-1;
}
ans[tmp.id]=res;
}
inline void get_ans(int now,int fa) {
if (w[now]!=-1) {
if (!lst[w[now]-1]) mn_to[now]=w[now];
else mn_to[now]=mn_to[lst[w[now]-1]];
lst.update(w[now],now);
}
for (res_v x:rs[now]) work(x);
for (int v:e[now]) if (v!=fa&&!del[v]) get_ans(v,now);
if (w[now]!=-1) lst.remove();
}
inline void calc(int now,vector<ques> tmp) {
c_res(now,0,0);
for (ques x:tmp) {
if (x.v==now) ans[x.id]=mx_res[x.u];
else rs[x.v].push_back({mx_res[x.u],x.id});
}
for (int v:e[now]) if (!del[v]) get_ans(v,now);
}
inline void clear_all() {
for (int x:pt) {
col[x]=mx_res[x]=mn_to[x]=mx_to[x]=0;
rs[x].clear();
}
pt.clear();
f(i,1,col_tot) col_s[i]=0;
col_tot=0;
}
inline void solve(int now,vector<ques> qnow) {
del[now]=1;
pt.push_back(now);
for (int v:e[now]) if (!del[v]) {
col_tot++;
col_s[col_tot]=v;
get_color(v,now,col_tot);
}
vector<ques> nows;
for (ques x:qnow) {
if (col[x.u]!=col[x.v]) nows.push_back(x);
else {
if (!col[x.u]) ans[x.id]=(w[now]==1);
else qnxt[col_s[col[x.u]]].push_back(x);
}
}
calc(now,nows);
vector<v_ques> qset;
for (int v:e[now]) if (!del[v]) {
if (qnxt[v].empty()) continue;
qset.push_back({qnxt[v],v});
qnxt[v].clear();
}
clear_all();
for (v_ques nxt:qset) {
int v=nxt.v;
rt=0;sum_siz=siz[v];
get_rt(v,now);
solve(rt,nxt.qs);
}
}
int main() {
read(n);read(m);read(C_z);
f(i,1,C_z) {int x;read(x);c_mp[x]=i;}
f(i,1,n) {
int x;read(x);
if (c_mp[x]) w[i]=c_mp[x];
else w[i]=-1;
}
f(i,2,n) {
int u,v;read(u);read(v);
e[u].push_back(v);
e[v].push_back(u);
}
read(qsum);
vector<ques> qset;
f(i,1,qsum) {
int u,v;read(u);read(v);
qset.push_back({u,v,i});
}
wgh[0]=inf;sum_siz=n;
get_rt(1,0);solve(rt,qset);
f(i,1,qsum) printf("%d\n",ans[i]);
return 0;
}
```
:::