树上莫队
cpp
namespace MoOnTree{
// 树上莫队
struct Node{
int id,l,r,p;
};
// be块编号，[L,R]块边界，seq括号序，in入序，out出序，dep深度
// par父节点数组，adj邻接表
// top括号序长度，block块大小，tot块数量
vector<int> be,L,R,seq,in,out,dep;
vector<vector<int>> par,adj;
int top,block,tot;
vector<Node> que;// 询问
vector<int> st;// 状态数组
bool cmp(const Node &x,const Node &y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
}
void dfs(int u,int fa){
seq[++top]=u;
in[u]=top;
par[u][0]=fa;
dep[u]=dep[fa]+1;
for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
}
seq[++top]=u;
out[u]=top;
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
if(u==v)return u;
for(int i=__lg(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
return par[u][0];
}
void assign(int n){
seq.assign(2*n+1,0);
in.assign(n+1,0);
out.assign(n+1,0);
dep.assign(n+1,0);
par.assign(n+1,vector<int>(__lg(n)+1,0));
st.assign(n+1,0);
adj.assign(n+1,{});
que.clear();
top=0;
}
void init(){
dfs(1,0);
block=(int)sqrt(top)+1,tot=(top+block-1)/block;
be.assign(top+1,0);
L.assign(tot+1,0);
R.assign(tot+1,0);
for(int i=1;i<=tot;i++){
L[i]=block*(i-1)+1,R[i]=min(block*i,top);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add_query(int u,int v){
if(in[u]>in[v])swap(u,v);
int p=lca(u,v);
int id=que.size();
if(p==u)que.push_back({id,in[u],in[v],0});
else que.push_back({id,out[u],in[v],p});
}
void addEdge(int u,int v){
adj[u].push_back(v);
}
}
using namespace MoOnTree;
void solve(){
int n,q;
cin>>n>>q;
vector<int> nums,w(n+1);
for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
assign(n);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
addEdge(u,v);
addEdge(v,u);
}
init();
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
add_query(x,y);
}
auto work=[&](){
sort(que.begin(),que.end(),cmp);
int res=0,l=1,r=0;
vector<int> ans(que.size());
vector<int> cnt(nums.size());
auto add=[&](int x){
st[x]^=1;
if(!st[x]){
if(!(--cnt[w[x]]))res--;
}
else{
if(!(cnt[w[x]]++))res++;
}
};
for(auto [id,ql,qr,p]:que){
while(r<qr)add(seq[++r]);
while(r>qr)add(seq[r--]);
while(l<ql)add(seq[l++]);
while(l>ql)add(seq[--l]);
if(p)add(p);
ans[id]=res;
if(p)add(p);
}
return ans;
};
for(auto x:work())cout<<x<<"\n";
}