题目描述
给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。
查询操作给定参数 \(l\ r\ x\)，需输出：
将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。
每次查询操作独立。
对于 \(100\%\) 的数据，所有出现过的数在 \([1,10^5]\) 之间，保证每次输入的 \(l \le x \le r\)。
题解
建出点分树，可以发现这样一个性质，对于树上任意一个连通块，一定有一个连通块上的点，在点分树该点的子树中包含连通块的所有点
那么对于每个询问中的\(x\)，我们找到它在点分树上一个深度最低的祖先\(v\)，满足\(v\)与\(x\)可以通过\([l,r]\)之间的点连通，那么问题就变成了求\(v\)所在连通块中颜色种类数，连通块只会在\(v\)的点分树子树内，这就变得很好做，一个点和\(v\)是否连通可以求出它到\(v\)的编号最小值\(\min\)和最大值\(\max\)，它与\(v\)连通当且仅当\(l\le\min,\max\le r\)，二维数点即可
\(\text{code}\)
#include<cstdio>
#include<algorithm>
using namespace std;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=2e5+100;
int n,q,a[N+10],st[N+10],tot;
struct edge
{
int to,last;
}e[N<<1|1];
void add(int a,int b)
{
e[++tot].to=b;
e[tot].last=st[a];
st[a]=tot;
}
struct node
{
int l,r,id;
};
vector<node> p[N+10];
int rt,siz[N+10],sum,ans[N+10];
bool vis[N+10];
void getrt(int u,int fa)
{
siz[u]=1;
int maxn=0;
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(v==fa||vis[v]) continue;
getrt(v,u),siz[u]+=siz[v],maxn=max(maxn,siz[v]);
}
maxn=max(maxn,sum-siz[u]);
if((maxn<<1)<=sum) rt=u;
}
int cnt;
struct qst
{
int id,l,r,co;
}g[N+10];
bool cmp(qst a,qst b){return a.l>b.l||(a.l==b.l&&a.r<b.r||a.l==b.l&&a.r==b.r&&a.id<b.id);}
int pre[N+10];
void dfs(int u,int minn,int maxn,int fa)
{
minn=min(minn,u),maxn=max(maxn,u);
g[++cnt]=(qst){0,minn,maxn,a[u]};
for(auto v:p[u])
if(v.l<=minn&&maxn<=v.r&&!ans[v.id])
g[++cnt]=(qst){v.id,v.l,v.r,0};
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(v==fa||vis[v]) continue;
dfs(v,minn,maxn,u);
}
}
struct Tree
{
int t[N+10];
int lowbit(int x){return x&-x;}
void update(int x,int k){for(;x<=N;x+=lowbit(x))t[x]+=k;}
int query(int x)
{
int res=0;
for(;x;x-=lowbit(x)) res+=t[x];
return res;
}
}t;
void solve(int u)
{
getrt(u,0),sum=siz[u],getrt(u,0),u=rt;
cnt=0;
dfs(u,N,0,0);
sort(g+1,g+1+cnt,cmp);
for(int i=1;i<=cnt;i++)
{
if(g[i].id==0)
{
if(!pre[g[i].co]) t.update(g[i].r,1),pre[g[i].co]=g[i].r;
else
{
if(g[i].r<pre[g[i].co])
t.update(pre[g[i].co],-1),t.update(g[i].r,1),pre[g[i].co]=g[i].r;
}
}
else ans[g[i].id]=t.query(g[i].r);
}
for(int i=1;i<=cnt;i++)
if(g[i].id==0&&pre[g[i].co])
t.update(pre[g[i].co],-1),pre[g[i].co]=0;
vis[u]=true;
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(vis[v]) continue;
solve(v);
}
}
int main()
{
// freopen("a.in","r",stdin);
read(n),read(q);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1,a,b;i<n;i++) read(a),read(b),add(a,b),add(b,a);
for(int i=1,l,r,x;i<=q;i++) read(l),read(r),read(x),p[x].push_back({l,r,i});
solve(1);
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}