[省选联考2021] 宝石
给定一棵 \(n\) 个点的树，每个点上有一颗种类是 \(w_i\) 的宝石，宝石种类共 \(m\) 种，有一个收集器，按照 \(P_1,P_2,...,P_c\) 的先后顺序收集宝石（就是说必须收集了前面的，才会收集后面的），有 \(q\) 次询问 $(s,t) $ ，询问从 \(s\) 到 \(t\) 最多 能收集多少宝石，若当前走到的点的宝石与当前需要放入的宝石种类一致才可以收集（也可以选择不收集）。
保证 \(p\) 中的值互不相同。
\(1\le n,q\le2\times10^5\) ，\(1\le c,m\le5\times10^4\)，\(1\le w_i\le m\) 。
有启发性的部分分： \(m\le300\) 。
Solution
每组询问暴力模拟，向上到 \(lca\) ，再向下找匹配的宝石一步步走，复杂度 \(O(nq)\) ，期望得分 \(25\) 分。
若考虑每次只走一步，这样必然很劣，注意到 \(m\le300\) 的部分分，如果每次都能一步走到需要加入的宝石的位置，则优秀一些，于是考虑预处理 \(f[i][j]\) 表示点 \(i\) 的祖先中第一个宝石种类为 \(j\) 的位置，转移只需考虑父亲的信息以及自身的颜色，但注意到这样做的话，从 \(lca\) 到 \(t\) 的路径不能直接处理，所以我们先只讨论向上跳的情况，到这一步的话，预处理是 \(O(nm)\) ，向上最多跳 \(c\) 次，我们认为 \(c\) 与 \(m\) 同阶，复杂度是 \(O((n+q)m)\) ，若可以处理向下移动，则期望得分 \(50\) 分。
事实上，这一档部分分是很有启发性的，这些移动，无非是一个逼近 \(lca\) 的过程，你思考你是怎么在 \(log\) 时间求出 \(lca\) 的，自然考虑倍增。
为方便维护，我们将宝石重新编号，不在需要收集的 \(c\) 种宝石中的宝石编号为 \(0\) ，\(P_1,...,P_c\) 号宝石编号为 \(1,2,...,c\) ，这样处理，向上的路径只需要找当前编号 \(+1\) ，那现在考虑向下的路径，类似的，只需要找当前编号 \(-1\) （因为逆序）。
那么我们就处理两个倍增数组 \(f1[u][i],f2[u][i]\) ，分别表示从点 \(u\) 向上跳 \(2^i\) 步递增和递减到达的点，这时若发现从 \(s\) 开始走一个 \(f1[s][i]\) 仍然不超过 \(lca\) ，则将向上部分的答案 \(s1\) 加上 \(2^i\) （不是 \(1\) ），注意，此处 “跳一步” 指的并不是儿子跳到父亲，而是跳到下一个需要收集的宝石所在的树上位置。
这个在树上只需在 \(dfs\) 过程中维护一个数组 \(t[i]\) 表示走到当前节点， 第 \(i\) 种宝石最后一次出现的位置，注意每次结束当前子树的 \(dfs\) 后，要把 \(t\) 数组复原（每次只修改一个位置，所以是 \(O(1)\) 复原）。
现在我们需要解决的就是向下路径的问题，考虑二分答案 \(mid\) ，表示当前这次询问一共收集了多少宝石，那么，只需要从 \(t\) 开始向上找到第一个种类为 \(mid\) 的宝石（注意是重新编了号的），这个信息不正是 \(t\) 数组所维护的吗？所以我们只需要对询问进行离线，对每个节点 \(i\) 开一个 \(vector\) ，表示以 \(i\) 为终点的询问，每次 \(dfs\) 到这个点时，就解决这个 \(vector\) 的询问，因为这时的 \(t\) 数组存的也正是我们需要的信息，设第一个种类为 \(mid\) 的宝石是 \(x\) ，答案的判定只需看 \(x\) 是否能至少向上跳 \(mid-s1\) 步仍不超过 \(lca\) 即可。
事实上询问还有一个问题，就是需要找到从 \(s\) 开始，第一个能够匹配的宝石，也即种类为 \(P_1\) 的宝石，先走这样一步，再进行上述的一系列操作，这个信息仍然是我们的 \(t\) 数组维护的，但这些所有的维护信息写在同一个 \(dfs\) 里就会有些繁杂不清，所以两遍 \(dfs\) 即可维护上述所有信息。
二分里面需要倍增数组判定，故时间复杂度 \(O(nlog^2n+q)\) 。
#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define inf 1e7
using namespace std;
int pd,lca,l,r,ans[N],n,m,c,q,A,B,dep[N],t[N],flag,a[N],f[N][19],first[N],f1[N][19],f2[N][19];
vector<int>v[N];
struct node
{
int s,t,id;
};
vector<node>ask[N];
int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
int tmp=t[a[u]];
t[a[u]]=u;first[u]=t[1];
f[u][0]=fa;f1[u][0]=t[a[u]+1];f2[u][0]=t[a[u]-1];
for(int i=1;i<=18;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
f1[u][i]=f1[f1[u][i-1]][i-1];
f2[u][i]=f2[f2[u][i-1]][i-1];
}
for(auto x:v[u])
{
if(x==fa) continue;
dfs(x,u);
}
t[a[u]]=tmp;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=18;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
}
for(int i=18;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int check(int u,int mid)
{
u=t[mid];
if(dep[u]<dep[lca]) return 0;
for(int i=18;i>=0;i--)
{
if(dep[f2[u][i]]>=dep[lca]) u=f2[u][i],mid-=(1<<i);
if(mid<=pd) return 1;
}
return 0;
}
void dfs2(int u,int fa)
{
int tmp=t[a[u]];
t[a[u]]=u;
for(auto x:ask[u])
{
lca=LCA(x.s,x.t);
int now=0,val=0;
if(dep[first[x.s]]>=dep[lca]) now=first[x.s];
if(now)
{
val++;
for(int i=18;i>=0;i--)
{
if(dep[f1[now][i]]>=dep[lca]) now=f1[now][i],val+=(1<<i);
}
}
pd=val+1;
l=val+1;r=c;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(u,mid)) val=mid,l=mid+1;
else r=mid-1;
}
ans[x.id]=val;
}
for(auto x:v[u])
{
if(x==fa) continue;
dfs2(x,u);
}
t[a[u]]=tmp;
}
int main()
{
n=read();m=read();c=read();
for(int i=1;i<=c;i++) A=read(),t[A]=i;
for(int i=1;i<=n;i++) a[i]=read(),a[i]=t[a[i]];
memset(t,0,sizeof(t));
for(int i=1;i<=n-1;i++)
{
A=read();B=read();
v[A].push_back(B);
v[B].push_back(A);
}
dfs(1,0);
q=read();
for(int i=1;i<=q;i++)
{
A=read();B=read();
ask[B].push_back((node){A,B,i});
}
memset(t,0,sizeof(t));
dfs2(1,0);
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}