很容易考虑到计算贡献。
该问题的关键在于——如何使得钥匙和宝箱的对应关系不算重
Warning：有这样的二元对应关系，可以考虑一下转化为括号序列！
转化为括号序列之后，发现路径上括号串的对应关系能够预处理出来。
套个虚树和扫描线，就做完了。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10,M=1e6+10;
int n,m,a[N],b[N];
vector<int>A[N];
int dft,bg[N],ed[N],dep[N],fa[N];
namespace QTree{
int dft,pos[N],top[N],son[N],siz[N];
void dfs1(int u){
dep[u]=dep[fa[u]]+1,siz[u]=1;
for(int v:A[u])if(v^fa[u]){
fa[v]=u,dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t,pos[bg[u]=++dft]=u;
if(son[u])dfs2(son[u],t);
for(int v:A[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
ed[u]=dft;
}
void init(){
dfs1(1),dfs2(1,1);
}
int LCA(int u,int v){
for(;top[u]^top[v];u=fa[top[u]]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
}
return dep[u]<dep[v]?u:v;
}
int kth(int u,int k){
for(;dep[u]-dep[top[u]]<k;u=fa[top[u]])k-=dep[u]-dep[top[u]]+1;
return pos[bg[u]-k];
}
}
using QTree::LCA;
using QTree::kth;
vector<int>pos[N],B[N];
int top,stk[N];
void add(int u,int v){
B[u].push_back(v),B[v].push_back(u);
}
int tag[N];
bool isin(int u,int t){
return bg[t]<=bg[u]&&bg[u]<=ed[t];
}
struct opts{
int l,r,x;
};
vector<opts>o[N];
void update(int x,int y,int l,int r){
if(x>y||l>r)return;
o[x].push_back({l,r,1}),o[y+1].push_back({l,r,-1});
}
void insert(int u,int v){
// fprintf(stderr,"%d %d\n",u,v);
if(isin(u,v)){
int x=kth(u,dep[u]-dep[v]-1);
update(bg[u],ed[u],1,bg[x]-1);
update(bg[u],ed[u],ed[x]+1,n);
}
else if(isin(v,u)){
int x=kth(v,dep[v]-dep[u]-1);
update(1,bg[x]-1,bg[v],ed[v]);
update(ed[x]+1,n,bg[v],ed[v]);
}
else{
update(bg[u],ed[u],bg[v],ed[v]);
}
}
void ins(int s,int u,int fa=0,int now=0){
now+=tag[u];
if(!now)return insert(s,u);
for(int v:B[u])if(v^fa)ins(s,v,u,now);
}
void clr(int u,int fa=0){
for(int v:B[u])if(v^fa)clr(v,u);
B[u].clear();
}
void solve(vector<int>&p){
if(p.empty())return;
sort(p.begin(),p.end(),[](int x,int y){return bg[x]<bg[y];});
stk[top=1]=p[0];
for(int len=p.size(),i=1;i<len;i++){
int x=LCA(stk[top],p[i]);
for(;top>1&&dep[stk[top-1]]>=dep[x];top--)add(stk[top-1],stk[top]);
if(stk[top]^x)add(x,stk[top--]);
if(stk[top]^x)stk[++top]=x;
if(stk[top]^p[i])stk[++top]=p[i];
}
for(int i=1;i<top;i++)add(stk[i],stk[i+1]);
for(int u:p)tag[u]=3-a[u]*2;
for(int u:p)if(tag[u]>0)ins(u,u);
clr(stk[1]);
for(int u:p)tag[u]=0;
}
namespace BIT{
int c[N];
void add(int x,int y){
for(;x<=n;x+=x&-x)c[x]+=y;
}
void get(int x,int &y){
for(y=0;x;x^=x&-x)y+=c[x];
}
}
vector<pair<int,int> >q[N];
int ans[M];
int main(){
freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
A[u].push_back(v),A[v].push_back(u);
}
QTree::init();
for(int i=1;i<=n;i++)pos[b[i]].push_back(i);
for(int i=1;i<=n;i++)solve(pos[i]);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
q[bg[u]].push_back({bg[v],i});
}
for(int i=1;i<=n;i++){
for(opts x:o[i])BIT::add(x.l,x.x),BIT::add(x.r+1,-x.x);
for(auto x:q[i])BIT::get(x.first,ans[x.second]);
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}