题目

给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。

查询操作给定参数 \(l\) \(r\) \(x\)，需输出：

将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。

每次查询操作独立。

分析

首先点分治能够通过经过当前重心的连通块表示出所有的连通块，

考虑一个点 \(y\) 处在 \(x\) 的连通块中

当且仅当 \(x\) 到 \(y\) 的路径上的点下标在 \([l,r]\) 范围内。

那么每次分治到一个新的重心，求出每个点到根节点的最小下标 \(L\) 和最大下标 \(R\)。

可以发现这个询问可以在这个重心被计算当且仅当 \(l\leq L\leq R\leq r\)，并且只要询问过就不需要递归下去。

那么只要这个条件满足就把它加入待询问的数组中，相当于在该重心的子树中提供 \((L,R,Col)\)，询问颜色个数。

那么将询问和这些点均按 \(l\) 从大到小排序，然后对于颜色记录前驱（HH的项链），

尽量使其出现的右端点尽量靠左（取最小值），然后用树状数组维护不超过其右端点的右端点个数。

时间复杂度 \(O((n+Q)\log ^2n)\)

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=100011; struct node{int y,next;}e[N<<1]; struct rec{int l,r,z;}E[N],b[N];
int siz[N],big[N],as[N],hs[N],rk[N],n,et=1,Q,ans[N],v[N],root,tot,TOT,a[N],las[N],c[N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
void update(int x,int y){
	for (;x<=n;x+=-x&x) c[x]+=y;
}
int query(int x){
	int ans=0;
	for (;x;x-=-x&x) ans+=c[x];
	return ans;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return ay.l;}
bool cmp1(int x,int y){return E[x].l>E[y].l;}
void Dp(int x){
	v[x]=1,tot=TOT=0,Dfs(x,0,x,x);
	sort(b+1,b+1+tot,cmp0),sort(rk+1,rk+1+TOT,cmp1);
	int j=1;
	for (int i=1;i<=TOT;++i){
		for (;j<=tot&&b[j].l>=E[rk[i]].l;++j)
		if (las[b[j].z]>b[j].r){
			update(las[b[j].z],-1);
			update(las[b[j].z]=b[j].r,1);
		}
		ans[rk[i]]=query(E[rk[i]].r);
	}
	for (int i=1;i