TLE #16,17,21 淀粉质

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+1;
int n,m,x,y,opt,a[N],ans[N];
int mxp[N],siz[N],rt=0;
int L[N],R[N],son[N],tot=0;
int lst[N],tree[N];
int head[N*2],nxt[N*2],to[N*2],cnt=-1;
bool vis[N];
struct node{
	int l,r,id;
	bool operator <(const node &b)const{
		return r<b.r;
	}
}que[N],col[N];
vector<node>q[N];
int max(register int a,register int b){
	return (a>b?a:b);
}
void get(register int u,register int fa,register int cnt){
	mxp[u]=0,siz[u]=1;
	for(register int i=head[u];~i;i=nxt[i]){
		register int v=to[i];
		if(v==fa||vis[v])continue;
		get(v,u,cnt);
		siz[u]+=siz[v];
		mxp[u]=max(mxp[u],siz[v]);
	}
	mxp[u]=max(mxp[u],cnt-siz[u]);
	if(mxp[u]<mxp[rt])rt=u;
}
void dfs(register int u,register int fa){
	siz[u]=1;
	son[++tot]=u;
	for(register int i=head[u];~i;i=nxt[i]){
		register int v=to[i];
		if(v==fa||vis[v])continue;
		L[v]=min(L[u],v),R[v]=max(R[u],v);
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
void add(register int x,register int d){
	if(!x)return;
	while(x<=n){
		tree[x]+=d;
		x+=x&(-x);
	}
}
int ask(register int x){
	register int sum=0;
	while(x){
		sum+=tree[x];
		x-=x&(-x);
	}
	return sum;
}
void solve(register int u){
	vis[u]=1;
	tot=0,L[u]=R[u]=u;
	dfs(u,0);
	register int res=0,flag=1;
	for(register int i=1;i<=tot;i++){
		register int v=son[i];
		lst[a[v]]=0;
		col[i]={L[v],R[v],a[v]};
		for(register int j=q[v].size()-1;~j;j--){
			if(q[v][j].l<=L[v]&&R[v]<=q[v][j].r){
				que[++res]=q[v][j];
				q[v].erase(q[v].begin()+j);
			}
		}
	}
	sort(col+1,col+1+tot);
	sort(que+1,que+1+res);
	for(register int i=1,j=1;i<=res;i++){
		while(j<=tot&&col[j].r<=que[i].r){
			if(lst[col[j].id]<col[j].l){
				add(lst[col[j].id],-1);
				lst[col[j].id]=col[j].l;
				add(lst[col[j].id],1);
			}
			j++;
		}
		ans[que[i].id]=ask(que[i].r)-ask(que[i].l-1);
	}
	for(register int i=1;i<=tot;i++){
		register int v=son[i];
		add(lst[a[v]],-1);
		lst[a[v]]=0;
		if(!q[v].empty())flag=1;
	}
	if(!flag)return;
	for(register int i=head[u];~i;i=nxt[i]){
		register int v=to[i];
		if(vis[v])continue;
		rt=0,get(v,0,siz[v]);
		solve(v);
	}
}
namespace IO{
	inline char getchar(){
		static const int maxbuf=65536;
		static char ibuf[maxbuf+1],*cur=ibuf+maxbuf;
	    return (cur==ibuf+maxbuf)?(fread(cur=ibuf,1,maxbuf,stdin),*cur++):*cur++;
	}
	void read(register int &x){
		x=0;
		char t=getchar();
		while(!isdigit(t))t=getchar();
		while(isdigit(t))x=x*10+t-'0',t=getchar();
		return;
	}
}
using IO::read;
static inline void write(register int x){
    if(x>9)write(x/10);
    putchar((x%10)|48);
}
int main(){
	read(n),read(m);
	for(register int i=1;i<=2*n;i++)head[i]=-1;
	for(register int i=1;i<=n;i++)read(a[i]);
	for(register int i=1;i<n;i++){
		read(x),read(y);
		nxt[++cnt]=head[x],head[x]=cnt,to[cnt]=y;
		nxt[++cnt]=head[y],head[y]=cnt,to[cnt]=x;
	}
	for(register int i=1;i<=m;i++){
		read(x),read(y),read(opt);
		q[opt].emplace_back((node){x,y,i});
	}
	mxp[0]=N;
	get(1,0,n);
	solve(rt);
	for(register int i=1;i<=m;i++){
		write(ans[i]);
		puts("");
	}
	return 0;
}