「Ynoi2011」成都七中
题意：询问 \(([l,r],x)\)，表示将树中编号在 \([l,r]\) 内的所有节点保留，求 \(x\) 所在连通块中颜色种类数
可以转化为从 \(x\) 出发且只经过节点范围在 \([l,r]\) 的路径上的颜色种类数，是路径问题且多次询问，所以可以考虑点分树
但是可以发现，一个节点的答案可以是往子树方向走的路径，还有往父节点而点分树不太好处理的路径；此时能发现一个性质，如果 \(x\) 可以只经过 \([l,r]\) 的路径到达 \(y\)，那么 \(([l,r],x)=([l,r],y)\)，于是我们可以找到 \(x\) 的点分树祖先中深度最小的节点 \(p\)，将询问 \(([l,r],x)\) 变为 \(([l,r],p)\)，那么此时只有往子树方向走的路径了
考虑如何统计答案，记当前节点为 \(u\)，\(dmin(u,x),dmax(u,x)\) 表示从 \(u\) 到 \(x\) 经过路径上最小、最大的节点编号，那么 \(x\) 对 \(u\) 有贡献当且仅当 \(l \le dmin(u,x)\) 且 \(dmax(u,x) \le r\)，可以发现是个二维偏序，排序处理右区间，树状数组处理左区间，具体来说，记录每种颜色左区间的最大值，用树状数组维护每个位置上的数量（同\(P1972\)）
#include<bits/stdc++.h>
using namespace std;
struct question{
int d,l,r;
bool operator<(const question &k)const{
return r<k.r;
}
};
int n,m,l,r,x,rt=-1,k,c[100001],fa[100001],vis[100001],siz[100001],dp[100001],ans[100001],t[100001],lst[100001],mx[100001][21],mn[100001][21],st[100001][21],dep[100001];
vector <int> G[100001],T[100001];
vector <question> V,Q[100001];
void add(int x,int v){
for(int i=x;i<=n;i+=i&-i) t[i]+=v;
}
int ask(int x){
int res=0;
for(int i=x;i>=1;i-=i&-i) res+=t[i];
return res;
}
void init(int u,int f){
dep[u]=dep[f]+1;
st[u][0]=mn[u][0]=mx[u][0]=f;
for(int i=1;i<=20;i++){
st[u][i]=st[st[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[st[u][i-1]][i-1]);
mx[u][i]=max(mx[u][i-1],mx[st[u][i-1]][i-1]);
}
for(int i=0;i<G[u].size();i++) if(G[u][i]!=f) init(G[u][i],u);
}
question get(int u,int v){
int r1=min(u,v),r2=max(u,v);
if(dep[u]<dep[v]) swap(u,v);
for(int i=20;i>=0;i--){
if(dep[st[u][i]]>=dep[v]){
r1=min(r1,mn[u][i]);
r2=max(r2,mx[u][i]);
u=st[u][i];
}
}
if(u==v) return {0,r1,r2};
for(int i=20;i>=0;i--){
if(st[u][i]!=st[v][i]){
r1=min(r1,min(mn[u][i],mn[v][i]));
r2=max(r2,max(mx[u][i],mx[v][i]));
u=st[u][i];
v=st[v][i];
}
}
return {0,min(r1,st[u][0]),max(r2,st[u][0])};
}
void find(int u,int f,int s){
siz[u]=1;
dp[u]=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]&&v!=f){
find(v,u,s);
siz[u]+=siz[v];
dp[u]=max(dp[u],siz[v]);
}
}
dp[u]=max(dp[u],s-siz[u]);
if(rt==-1||dp[rt]>dp[u]) rt=u;
}
void build(int u){
vis[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]){
rt=-1;
find(v,0,siz[v]);
find(rt,0,siz[v]);
fa[rt]=u;
T[u].push_back(rt);
build(rt);
}
}
}
void dfs(int u,int f,int L,int R){
V.push_back({u,L,R});
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]&&v!=f) dfs(v,u,min(L,v),max(R,v));
}
}
void solve(int u){
vis[u]=1;
V.clear();
dfs(u,0,u,u);
sort(V.begin(),V.end());
for(int i=0,now=0;i<Q[u].size();i++){
while(now<V.size()&&V[now].r<=Q[u][i].r){
int col=c[V[now].d];
if(!lst[col]) add(lst[col]=V[now].l,1);
else if(lst[col]<V[now].l) add(lst[col],-1),add(lst[col]=V[now].l,1);
now++;
}
ans[Q[u][i].d]=ask(Q[u][i].r)-ask(Q[u][i].l-1);
}
for(int i=0;i<V.size();i++) if(lst[c[V[i].d]]) add(lst[c[V[i].d]],-1),lst[c[V[i].d]]=0;
for(int i=0;i<T[u].size();i++) solve(T[u][i]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=2;i<=n;i++){
scanf("%d%d",&l,&r);
G[l].push_back(r);
G[r].push_back(l);
}
init(1,0);
find(1,0,n);
find(rt,0,n);
build(k=rt);
memset(vis,0,sizeof(vis));
for(int i=1,now;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
for(int j=x;j;j=fa[j]){
question val=get(x,j);
if(val.l>=l&&val.r<=r) now=j;
}
Q[now].push_back({i,l,r});
}
for(int i=1;i<=n;i++) sort(Q[i].begin(),Q[i].end());
solve(k);
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}