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,n]\) 的序列，再对点权做同样转化，这样就变成了求路径形如 \(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)\) 的时间内解决问题。
代码

1. #include<bits/stdc++.h>
2. #define endl '\n'
3. #define rep(i,a,b) for(ll i=(a);i<=(b);++i)
4. using namespace std;
5. typedef long long ll;
6. const ll MAXN=2e5+5;
7. const ll MAXC=5e4+5;
8. ll n,m,c;
9. ll p[MAXN],w[MAXN],Id[MAXN];
10. void init_w(){
11.         rep(i,1,c){
12.                 Id[p[i]]=i;
13.                 p[i]=i;
14.         };
15.         rep(i,1,n){
16.                 w[i]=Id[w[i]];
17.         };
18. }
19. vector<ll>adj[MAXN];
20. ll Q;
21. struct Query{
22.         ll s,t,md;
23. }q[MAXN];
24. ll fa[MAXN][22],dep[MAXN];
25. void infd(ll u,ll f){
26.         fa[u][0]=f;
27.         dep[u]=dep[f]+1;
28.         rep(i,1,20){
29.                 fa[u][i]=fa[fa[u][i-1]][i-1];
30.         };
31.         for(auto v:adj[u]){
32.                 if(v==f){
33.                         continue;
34.                 }
35.                 infd(v,u);
36.         }
37. }
38. ll lca(ll u,ll v){
39.         if(dep[u]>dep[v]){
40.                 swap(u,v);
41.         }
42.         ll cha=dep[v]-dep[u];
43.         for(int i=0;cha;++i){
44.                 if(cha&1){
45.                         v=fa[v][i];
46.                 }
47.                 cha>>=1;
48.         }
49.         if(u==v){
50.                 return u;
51.         }
52.         for(int i=20;i>=0;--i){
53.                 if(fa[u][i]!=fa[v][i]){
54.                         u=fa[u][i];
55.                         v=fa[v][i];
56.                 }
57.         }
58.         return fa[u][0];
59. }
60. namespace Zj{
61.         ll cls[MAXN],nxt[MAXN][22],cls1[MAXN];
62.         void dfsz(ll u){
63.                 ll ocls=cls[w[u]];
64.                 cls[w[u]]=u;
65.                 if(w[u]==1){
66.                         cls1[u]=u;
67.                 }else{
68.                         cls1[u]=cls1[fa[u][0]];
69.                 }
70.                 nxt[u][0]=cls[w[u]+1];
71.                 rep(i,1,20){
72.                         nxt[u][i]=nxt[nxt[u][i-1]][i-1];
73.                 };
74.                 for(auto v:adj[u]){
75.                         if(v==fa[u][0]){
76.                                 continue;
77.                         }
78.                         dfsz(v);
79.                 }
80.                 cls[w[u]]=ocls;
81.         };
82.         ll ans[MAXN];
83.         ll qryz(ll s,ll t){
84.                 s=cls1[s];
85.                 if(s==0||dep[s]<=dep[t]){
86.                         return 0;
87.                 }
88.                 for(int i=20;i>=0;--i){
89.                         if(dep[nxt[s][i]]>dep[t]){
90.                                 s=nxt[s][i];
91.                         }
92.                 }
93.                 return w[s];
94.         };
95.         void dfsf(ll u){
96.                 ll ocls=cls[w[u]];
97.                 cls[w[u]]=u;
98.                 nxt[u][0]=cls[w[u]-1];
99.                 rep(i,1,20){
100.                         nxt[u][i]=nxt[nxt[u][i-1]][i-1];
101.                 };
102.                 for(auto v:adj[u]){
103.                         if(v==fa[u][0]){
104.                                 continue;
105.                         }
106.                         dfsf(v);
107.                 }
108.                 cls[w[u]]=ocls;
109.         };
110.         vector<ll>qy[MAXN];
111.         ll check(ll id,ll s,ll T,ll v){
112.                 ll L=v+1,R=m,fans=v;
113.                 while(L<=R){
114.                         ll mid=(L+R)/2;
115.                         ll st=cls[mid];
116.                         for(int i=20;i>=0;--i){
117.                                 if(dep[nxt[st][i]]>=dep[T]){
118.                                         st=nxt[st][i];
119.                                 }
120.                         }
121.                         if(st==0||dep[st]<dep[T]||w[st]>v+1){
122.                                 R=mid-1;
123.                         }else{
124.                                 L=mid+1;
125.                                 fans=mid;
126.                         }
127.                 }
128.                 return fans;
129.         };
130.         void qryf(ll u){
131.                 ll ocls=cls[w[u]];
132.                 cls[w[u]]=u;
133.                 for(auto id:qy[u]){
134.                         ll md=q[id].md;
135.                         ans[id]=check(id,u,md,ans[id]);
136.                 }
137.                 for(auto v:adj[u]){
138.                         if(v==fa[u][0]){
139.                                 continue;
140.                         }
141.                         qryf(v);
142.                 }
143.                 cls[w[u]]=ocls;
144.         };
145.         void Do(){
146.                 dfsz(1);
147.                 rep(i,1,Q){
148.                         ll s=q[i].s,md=q[i].md;
149.                         ans[i]=qryz(s,md);
150.                 };
151.                 memset(nxt,0,sizeof(cls));
152.                 dfsf(1);
153.                 rep(i,1,Q){
154.                         ll t=q[i].t;
155.                         qy[t].push_back(i);
156.                 };
157.                 qryf(1);
158.                 rep(i,1,Q){
159.                         cout<>n>>m>>c;
160.         rep(i,1,c){
161.                 cin>>p[i];
162.         };
163.         rep(i,1,n){
164.                 cin>>w[i];
165.         };
166.         init_w();
168.         rep(i,1,n-1){
169.                 ll u,v;
170.                 cin>>u>>v;
171.                 adj[u].push_back(v);
172.                 adj[v].push_back(u);
173.         };
174.         infd(1,0);
175.         cin>>Q;
176.         rep(i,1,Q){
177.                 cin>>q[i].s>>q[i].t;
178.                 q[i].md=lca(q[i].s,q[i].t);
179.         };
180.         Zj::Do();
181.         return 0;
182. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！