P7518 [省选联考 2021 A/B 卷] 宝石
题目大意详细题目传送门
给出一棵树，树有点权,点权大小不超过 \(m\)，\(Q\) 组询问，每组询问 \(s,t\)。
给出 \(P_1\cdots P_c\)。
求最大的 \(v\) 使存在 \(s\rightarrow t\) 路径上的一个子序列匹配 \(P_1\cdots P_v\)。
\(n\leq 2\cdot 10^5,c\leq m\leq 5\cdot 10^4\)，\(P\) 互不相同。
思路
首先可以先将 \(P\) 变成 \(\) 的序列，再对点权做同样转化，这样就变成了求路径形如 \(1,2,3,\cdots\) 的最长子序列长度。通常这种题肯定是转化成记录 \(s\rightarrow lca(s,t)\) 的贡献和 \(lca(s,t)\rightarrow t\) 的贡献。
发现无论是要求还是难易度肯定是前者好求，于是先思考前者。对于朴素做法，直接一个个跳是不好的。发现我们首先可以尝试不去在所有情况下都一个个去跳。尝试对于每一个 \(u\),维护一个 \(X_u\) 表示 \(u\) 的祖先当中点权为 \(w_u+1\) 且深度最大的那一个。于是我们就可以从 \(s\) 的祖先中找到最深的 \(w_u=1\) 的点，然后每一次 \(u=X_u\)看到 \(lca(s,t)\) 之前能够跳到哪里。然后就是在深搜时维护一个 \(cls_v\) 表示在 \(u\) 的祖先当中深度最大且 \(w_u=v\) 的点。发现搜到一个 \(u\) 时，在子树中没有找到一个新的 \(w_{u'}=w_u\) 之前 \(cls_{w_u}=u\)，于是记录往下跳之前的 \(cls_{w_u}\) 然后在搜索时令 \(cls_{w_u}^{'}=u\) 即可。所以 \(X_u=cls_{w_u+1}\)。
之后就可以类似倍增处理，令 \(X^{'}_{u,i}\) 表示 \(u\) 的祖先中点权为 \(w_u+2^i\) 且深度最大的点。所以可以在满足 \(d_{X^{'}_{u,i}}>d_{lca(s,t)}\) 之前不断 \(u\leftarrow X^{'}_{u,i}\)（其中 \(d_u\) 指 \(u\) 的深度），并且之所以是 \(>\) 是因为我在这里处理默认是不处理 \(lca(s,t)\) 的，留给 \(lca(s,t)\rightarrow t\)。那么用 \(\log n\) 的时间完成了这一部分。
接下来开始处理\(lca(s,t)\rightarrow t\)。发现无法直接像上部分那样直接同理往下跳，因为不知道跳到哪里。然后看看能不能直接从 \(n\) 开始像上一题一样跳 \(n-1,n-2,\cdots\)，发现也不行。不妨设对于一个询问 \(i\) 我们 \(s\rightarrow lca(s,t)\) 跳到了 \(A_i\)。区别就在于上方做法我们只能这么跳且贪心最优，可是如果从 \(n\) 开始到根一定最优的，可是如果是到 \(lca(s,t)\) 就可能会出现绝大部分链都在 \(lca(s,t)\) 的上方，所以在下方也连不上 \(A_i\)，如:
如果我们从 \(7\) 开始跳的话最终路径拼接是 \(1\rightarrow 2\rightarrow 6\rightarrow 7\) 发现根本不合法长度只有 \(2\),不如 \(1\rightarrow 2\rightarrow 3\rightarrow 4\)。
但是观察到选择的权值是有单调性的。
如果选择的 \(x\) 不存在，那么所有大于 \(x\) 的想要接上去一定要从 \(x+1\rightarrow x\)，又因为不存在所以无法成功拼接。
如果存在 \(x\)，那么 \(x-1\) 也必须存在。所以一定是有一个 \(x\) 使得所有小于 \(x\) 的都存在且 \(x+1\) 不存在。
所以我们可以考虑二分，二分出一个 \(x\)。判断从最下方的 \(w_u=x\) 开始往上跳，跳到一个最接近 \(lca(s,t)\) 的 \(w_{u^{'}}=x-k\)。这时候我们判断 \(x-k\leq A_i+1\) 的话就说明可以拼接上，则往大考虑，否则往小考虑。对于跳的部分就还是可以类比上方做法只不过 \(X_u=cls_{w_u-1}\),\(X^{'}_{u,i}\) 表示 \(u\) 的祖先中点权为 \(w_u-2^i\) 且深度最大的点。
现在问题就变成了如何快速找到最下方满足 \(w_u=x\) 的点，即维护所有点的所有的 \(cls\)。如果比较一眼的话似乎可以树链剖分+主席树之类的做一做，可是会再多一些 \(\log\)，看起来不是很好接受。但是发现如果对于一个点我们可以求出 \(cls\)，于是考虑离线。对于一个点 \(u\)，我们可以直接访问所有形如 \((s,t=u)\) 的询问，这样的 \(cls\) 就是确定的。可以再去二分，这样就不用一直维护 \(cls\) 了，否则空间会爆炸。
那么我们就可以在 \(O(Q\log m\log n)\) 的时间内解决问题。
代码
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
const ll MAXC=5e4+5;
ll n,m,c;
ll p,w,Id;
void init_w(){
rep(i,1,c){
Id]=i;
p=i;
};
rep(i,1,n){
w=Id];
};
}
vector<ll>adj;
ll Q;
struct Query{
ll s,t,md;
}q;
ll fa,dep;
void infd(ll u,ll f){
fa=f;
dep=dep+1;
rep(i,1,20){
fa=fa];
};
for(auto v:adj){
if(v==f){
continue;
}
infd(v,u);
}
}
ll lca(ll u,ll v){
if(dep>dep){
swap(u,v);
}
ll cha=dep-dep;
for(int i=0;cha;++i){
if(cha&1){
v=fa;
}
cha>>=1;
}
if(u==v){
return u;
}
for(int i=20;i>=0;--i){
if(fa!=fa){
u=fa;
v=fa;
}
}
return fa;
}
namespace Zj{
ll cls,nxt,cls1;
void dfsz(ll u){
ll ocls=cls];
cls]=u;
if(w==1){
cls1=u;
}else{
cls1=cls1];
}
nxt=cls+1];
rep(i,1,20){
nxt=nxt];
};
for(auto v:adj){
if(v==fa){
continue;
}
dfsz(v);
}
cls]=ocls;
};
ll ans;
ll qryz(ll s,ll t){
s=cls1;
if(s==0||dep<=dep){
return 0;
}
for(int i=20;i>=0;--i){
if(dep]>dep){
s=nxt;
}
}
return w;
};
void dfsf(ll u){
ll ocls=cls];
cls]=u;
nxt=cls-1];
rep(i,1,20){
nxt=nxt];
};
for(auto v:adj){
if(v==fa){
continue;
}
dfsf(v);
}
cls]=ocls;
};
vector<ll>qy;
ll check(ll id,ll s,ll T,ll v){
ll L=v+1,R=m,fans=v;
while(L<=R){
ll mid=(L+R)/2;
ll st=cls;
for(int i=20;i>=0;--i){
if(dep]>=dep){
st=nxt;
}
}
if(st==0||dep<dep||w>v+1){
R=mid-1;
}else{
L=mid+1;
fans=mid;
}
}
return fans;
};
void qryf(ll u){
ll ocls=cls];
cls]=u;
for(auto id:qy){
ll md=q.md;
ans=check(id,u,md,ans);
}
for(auto v:adj){
if(v==fa){
continue;
}
qryf(v);
}
cls]=ocls;
};
void Do(){
dfsz(1);
rep(i,1,Q){
ll s=q.s,md=q.md;
ans=qryz(s,md);
};
memset(nxt,0,sizeof(cls));
dfsf(1);
rep(i,1,Q){
ll t=q.t;
qy.push_back(i);
};
qryf(1);
rep(i,1,Q){
cout<>n>>m>>c;
rep(i,1,c){
cin>>p;
};
rep(i,1,n){
cin>>w;
};
init_w();
rep(i,1,n-1){
ll u,v;
cin>>u>>v;
adj.push_back(v);
adj.push_back(u);
};
infd(1,0);
cin>>Q;
rep(i,1,Q){
cin>>q.s>>q.t;
q.md=lca(q.s,q.t);
};
Zj::Do();
return 0;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]