自动搬运

查看原文

来自洛谷，原作者为

	Gmt丶FFF 寄

搬运于2025-08-24 22:09:23，当前版本为作者最后更新于2023-10-09 19:40:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树德蒟蒻瑟瑟发抖。

文化课差考不起七中

首先因为这题求的东西与连通块有关，又有多组询问，可以想到与点分树有关，因为点分树上的一棵子树在原树上是一个连通块。

然后建出点分树后，就不知道怎么做了。

实际上呢，对于每一个询问，存在点分树上的一个点 $y\in[l,r]$ 包含整个 $x$ 所在满足 $\left[l,r\right]$ 限制的连通块。

证明是显然的，因为点分树最浅的在满足条件的联通块里的点子树为原树的连通块，此时若 $x$ 在子树且 $y$ 与 $x$ 处于连通块中，其他的点也会包含在此连通块中，不然就会跑到点分树上 $y$ 的祖先去了。

那么我们可以对于点分树上开始搜子树的节点，但是由于判 $x$ 与 $y$ 是否联通不能在点分树上判断，所以对于点分树上每一个点，在原树上进行搜索，记录路径上的最大编号与最小编号，搜到每个 $x$ 时，就可以判断是否联通了。

那么我们可以对于树上每个点我们可以建一个 vector，这样把每个询问的 $x$ push 进去即可。

现在我们就找到 $y$ 了，那么连通块上的点就是 $\text{路径上最大编号} \le r$ 且 $\text{路径上最小编号}\ge l$ 的点。（这个就应该不用证了吧）

那么假设我们要求的是求联通块的大小，那么我们因为有很多个询问对应一个 $y$，所以我们相当于就是有许多询问 $\left[l,r\right]$，很多个点 $\left[x,y\right]$，求有多少个点满足 $l\le x$ 且 $y \le r$，这很明显是个二维偏序问题，以 $r,y$ 为第一关键字排序，扫描 $r$，在满足 $y \le r$ 的情况下，用树状数组维护 $x$，根据 $l$ 来求出树状数组中数字之和即可。

现在有颜色的限制，实际上也很简单，在维护树状数组的过程中，判断这个颜色之前是否也有相同颜色的点加入过树状数组，如果有，我们留下 $x$ 更大的那个，这样造成的贡献更多，最后统一清空即可。

那么这样看下来，根本不需要建点分树了，点分治的途中维护即可。

但还是一打就打到头吧，最后还是建了点分树，主要是懒得改。

时间复杂度：$O(n\log_2^2n)$

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+5;
vector<int>a[N],b[N];
int n,m,rt,siz[N],mp[N],tot,vis[N],res[N],f[N],las[N],c[N],st[N],cnt;
struct node
{
	int id,l,r;
};
vector<node>q[N],p,w;
inline int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int k)
{
	while(x<=n)
	{
		f[x]+=k;
		x+=lowbit(x);
	}
}
int search(int x)
{
	int sum=0;
	while(x)
	{
		sum+=f[x];
		x-=lowbit(x);
	}
	return sum;
}
bool cmp(node x,node y)
{
	return x.r<y.r;
}
void findzx(int x,int fa)
{
	siz[x]=1;
	mp[x]=1;
	int len=a[x].size();
	for(int i=0;i<len;i++)
	{
		if(vis[a[x][i]]||a[x][i]==fa)continue;
		findzx(a[x][i],x);
		siz[x]+=siz[a[x][i]];
		mp[x]=max(mp[x],siz[a[x][i]]);
	}
	mp[x]=max(mp[x],tot-siz[x]);
	if(mp[rt]>mp[x])rt=x;
}
void divide(int x,int num)
{
	vis[x]=1;
	int len=a[x].size();
	for(int i=0;i<len;i++)
	{
		if(vis[a[x][i]])continue;
		if(siz[x]>siz[a[x][i]])tot=siz[a[x][i]];
		else tot=num-siz[x];
		rt=0;
		findzx(a[x][i],0);
		b[x].push_back(rt);
		divide(rt,tot);
	}
}
void dfs2(int x,int fa,int l,int r)
{
//	cout<<x<<" "<<fa<<" "<<l<<" "<<r<<endl;
	p.push_back({c[x],l,r});
	int len=q[x].size();
	for(int i=0;i<len;i++)if(!res[q[x][i].id]&&l>=q[x][i].l&&r<=q[x][i].r)w.push_back(q[x][i]);
	len=a[x].size();
	for(int i=0;i<len;i++)
	{
		if(a[x][i]==fa||vis[a[x][i]])continue;
		dfs2(a[x][i],x,min(l,a[x][i]),max(r,a[x][i]));
	}
}
void calc(int x)
{
	p.clear();
	w.clear();
//	cout<<x<<" :\n";
	dfs2(x,0,x,x);
	sort(p.begin(),p.end(),cmp);
	sort(w.begin(),w.end(),cmp);
	int head=0;
	int len=p.size(),len2=w.size();
	for(int i=0;i<len2;i++)
	{
//		cout<<x<<" "<<w[i].id<<"\n";
		while(head<len&&p[head].r<=w[i].r)
		{
//			cout<<head<<endl;
			if(!las[p[head].id])update(p[head].l,1),las[p[head].id]=p[head].l,st[++cnt]=p[head].id;
			else if(p[head].l>las[p[head].id])update(las[p[head].id],-1),update(p[head].l,1),las[p[head].id]=p[head].l;
//			cout<<head<<endl;
			head++;
		}
		res[w[i].id]=search(n)-search(w[i].l-1);
//		cout<<"!!\n";
	}
//	cout<<"///";
	while(cnt)update(las[st[cnt]],-1),las[st[cnt]]=0,cnt--;
}
void dfs(int x)
{
	calc(x);
	vis[x]=1;
	int len=b[x].size();
	for(int i=0;i<len;i++)dfs(b[x][i]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	mp[0]=2e9;
	tot=n;
	findzx(1,0);
	int root=rt;
	divide(rt,n);
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		q[x].push_back({i,l,r});
	}
	for(int i=1;i<=n;i++)vis[i]=0;
	dfs(root);
	for(int i=1;i<=m;i++)printf("%d\n",res[i]);
	return 0;
}