如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
我们发现，题目要求的是区间虚树的颜色个数，我们把询问离线，按右端点排序，维护每一个左端点的虚树的答案。
我们新加入一个点 $i$，虚树上最多加两个点，其中一个是这个点本身，影响到了左端点为 $[1,i]$ 的虚树。
另一个点我们在 LCT 上 access 一下，将这个点到根的链的权值赋值为 $i$。
access 时经过的每一条虚边的父亲就是可能的一个新增的节点，其影响到的虚树是一个前缀（其实是一个区间，但前面的每颗虚树都已经有这个点了，我们再加一遍也没事），前缀大小就是这个节点的权值。
那么现在问题变为，我们有 $n$ 个集合，$O(n\log n)$ 次修改，一次修改形如向一个前缀中加入一个颜色，一次查询形如单点查询集合大小。
我们对每种颜色记录当前长度为多少的前缀已经包含这种颜色，称为 $pos_i$，那么一次修改就是区间 $(pos_i,k]$ 加 1，$pos_i\larr \max(pos_i,k)$，一次查询就是单点查询，树状数组解决。
时间复杂度 $O(n\log^2n+m\log n)$，空间复杂度 $O(n+m)$。
#include<cstdio>
#include<vector>
#include<cmath>
#include<list>
#include<iterator>
#include<algorithm>
std::vector<std::pair<int,int>> v[100010],q[100010];
int n,m,col[100010],ans[500010],p[100010];
long long dep[100010];
int f[100010],s[100010][2],st[100010],tp,val[100010],tag[100010];
void dfs(int x,int fa){
f[x]=fa;
for(auto [u,d]:v[x])if(u!=fa){
dep[u]=dep[x]+d;
dfs(u,x);
}
}
int c[100010],pre[100010];
void update(int i){for(;i<=n;i+=i&-i)++c[i];}
void erase(int i){for(;i<=n;i+=i&-i)--c[i];}
int query(int i){int ans=0;for(;i;i&=i-1)ans+=c[i];return ans;}
void addtag(int x,int v){val[x]=tag[x]=v;}
void pushdown(int x){
if(tag[x]) addtag(s[x][0],tag[x]),addtag(s[x][1],tag[x]),tag[x]=0;
}
bool isroot(int x){return s[f[x]][0]!=x&&s[f[x]][1]!=x;}
void rotate(int x){
int y=f[x],z=f[y],w=s[y][1]==x;if(!isroot(y)) s[z][s[z][1]==y]=x;
f[y]=x,f[x]=z,f[s[x][w^1]]=y,s[y][w]=s[x][w^1],s[x][w^1]=y;
}
void splay(int x){
st[tp++]=x;for(int u=x;!isroot(u);u=st[tp++]=f[u]);
while(tp) pushdown(st[--tp]);
while(!isroot(x)){
if(!isroot(f[x]))rotate((s[f[x]][0]==x)^(s[f[f[x]]][0]==f[x])?x:f[x]);
rotate(x);
}
}
void upd(int col,int pos){
if(pre[col]<pos){
update(pre[col]+1);
erase((pre[col]=pos)+1);
}
}
void access(int z){
int x=z;
for(int y=0;x;y=x,x=f[x]){
splay(x),s[x][1]=y;
if(val[x]) upd(col[x],val[x]);
}
splay(z),addtag(z,z);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,d;i<n;i++) scanf("%d%d%d",&x,&y,&d),v[x].emplace_back(y,d),v[y].emplace_back(x,d);
dfs(1,0);
for(int i=1;i<=n;i++) p[i]=i;
std::sort(p+1,p+n+1,[](int x,int y){return dep[x]<dep[y];});
dep[0]=0x7fffffffffffffffll;
for(int i=1;i<=n;i++)
if(dep[p[i]]==dep[p[i-1]]) col[p[i]]=col[p[i-1]];
else col[p[i]]=i;
for(int i=1,l,r;i<=m;i++) scanf("%d%d",&l,&r),q[r].emplace_back(l,i);
for(int i=1;i<=n;i++){
upd(col[i],i);
access(i);
for(auto [l,id]:q[i]) ans[id]=query(l);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}