前言
青蛙。
树上ds好题，运用了很多巧妙的树上问题处理策略。
难度
2700。
题意简述
给定一棵 \(n\) 个点的树，每个节点上要么有一把钥匙，要么有一个宝箱，且钥匙和宝箱都是有颜色的，有 \(m\) 次询问 \((u,v)\) ，表示走树上 \(u\) 到 \(v\) 的路径，若当前点是钥匙，则接受，若是宝箱，则查看之前接受的钥匙是否存在和宝箱颜色相同的，若存在，则得分 \(+1\) ，每组询问独立，求每组询问的得分。
\(1\le n\le5\times10^5\) ，\(1\le m\le1\times10^6\) ，每种颜色的钥匙均不超过 \(5\) 。
Solution
首先，题目给出的特殊条件一定是出发点，相信出题人是不会平白无故给你神奇的性质的。
你发现直接对 \((u,v)\) 进行计算是很困难的，这时候我们通常是考虑贡献的转化，把 “直接算出当前的答案” 转化为 “哪些路径的加分能够贡献当前询问的路径” ，于是只需考虑一条路径能够对哪些其他的路径产生影响，这样就实现了思路和贡献的转化。
具体地，我们首先可以想到，对出现的每一种颜色分开考虑，我们每次枚举点对只需进行树的 \(dfs\) 即可。
对于当前考虑的颜色 \(col\) 来说，将这种颜色的钥匙设为 \(1\) ，这种颜色的宝箱设为 \(-1\) ，其他颜色不同的点，不论是钥匙还是宝箱都设为 \(0\) ，这样的话，我们从一个点开始树上 \(dfs\) ，当找到一个点的路径和等于 \(0\) 时，我们就不必再继续搜索下面的节点了。
这是为啥呢？其实是为了避免算重，我们这样考虑，假设从 \(S\) 点开始搜索，这个最先遇到的路径和为 \(0\) 的节点是 \(T\) ，那么对于树上所有横跨了路径 \((S,T)\) 的路径，都是会被 \((S,T)\) 贡献的（当然，由于 \(T\) 是第一次为零的位置，也即只在这一个位置产生 \(1\) 的得分）。
之后，如果继续搜索，又遇到一个使其为零的节点 \(U\) ，这时的得分显然就是 \(2\) 了，如果仍然将横跨 \((S,U)\) 的路径被当前这个 \(2\) 的得分贡献，那么你思考，\(2\) 的贡献咋来的，还不是 \((S,T)\) 产生了 \(1\) 的贡献，所以其实 \((S,T)\) 的贡献被计算了两次，故我们每次搜索过程中，只考虑第一个遇到的路径和为 \(0\) 的节点，这样才会避免上述算重的情况，且这样做显然是能够计算所有贡献的。
回头看看这个按颜色进行 \(dfs\) 的过程，你发现每次只需要从那 \(5\) 个颜色相同的钥匙开始做，但这样还是和对每个点进行整棵树的搜索别无二致，仍然是 \(O(N^2)\) 的复杂度，那怎么办呢？假设当前枚举到红色，我们看下面一个图。
（图源：Bindir0的ppt）
从根部的红色搜索到底部的红色，需要经过大量的蓝色点，但我们只关心第一次搜索到的位置，所以中间的大量蓝色点，我们是完全没有必要去搜索的，也就是说，每次只需要一部分关键节点，所以我们对每个颜色的关键点建出对应的虚树。
虚树，也即只保留关键点和他们的 \(LCA\) ，这样就维护了原本的信息结构，使得本来应该在某个点之后被搜索到的点仍然在其之和被搜索到，且节省了大量无用节点。
这样可知，每轮最多对虚树遍历 \(5\) 次，设有 \(k\) 个关键点，则虚树大小是 \(klogk\) 的，则总共也就是 \(nlogn\) 级别的。
下一个问题，如何将当前的 \(1\) ，贡献到横跨了 \((S,T)\) 的路径上去呢？
这个问题我们分三种情况讨论。
第一种，若 \(T\) 在 \(S\) 的子树内，则 \(S\) 除 \(T\) 所在子树的其他子树的所有点到 \(T\) 子树中的所有点构成的路径，都会被 \((S,T)\) 贡献 \(1\) ，也就是说，设 \(S\) 向 \(T\) 的方向的儿子为 \(son\) ，以 \(son\) 为根的子树内最大的 \(dfn\) 的值为 \(end[son]\) ，那么区间 \([1,dfn[son]-1]∪[end[son]+1,n]\) 中的点向区间 \([dfn[T],end[T]]\) 中的点行走时，都会被路径 \((S,T)\) 贡献。
第二种，若 \(S\) 在 \(T\) 的子树内，又设 \(T\) 向 \(S\) 的方向的儿子为 \(son\) ，于是同理有点集 \([dfn[S],end[S]]\) 到点集 \([1,dfn[son]-1]∪[end[son]+1,n]\) 会被 \((S,T)\) 贡献。
第三种， \(S,T\) 不存在祖先关系，也即前两种情况都不满足，这种情况反而更加简单，这时候只需 \(S\) 子树任意一点到 \(T\) 子树任意一点的路径，显然都会被贡献，也即点集 \([dfn[S],end[S]]\) 和点集 \([dfn[T],end[T]\) 。会被 \(S,T\) 贡献。
如何维护呢？我们用一个 \(n\times n\) 矩形来代表我们维护的任意两个点对的值，也即维护 \(A[i][j]\) ，表示 \(i\) 走到 \(j\) 的答案。
那么对于我们上述三种情况的讨论，我们只需执行对应的矩形加即可，也即把上述讨论中的两个区间，看成子矩形的边界，你发现没有修改，所以只需做二维差分，最后算每一行的总和时，使用一个树状数组维护即可，对于一个查询，实际上就是查询一个点值，由于维护的是差分，所以查的是前缀和。
时间复杂度 \(O((5n+m)logn)\) ，下面是我的代码。
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define mp make_pair
using namespace std;
int A,B,s[N],c[N],top[N],ans[N],rev[N],z,now,tot,f[N],cnt,dfn[N],n,m,op[N],col[N],dep[N],siz[N],son[N];
char *p1,*p2,buf[100000];
#define getc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x=0,f=1;char ch=getc();
while(ch<48||ch>57){if(ch=='-')f=-1;ch=getc();}
while(ch>=48&&ch<=57){x=x*10+ch-48,ch=getc();}
return x*f;
}
vector<int>v[N],G[N],tmp,vec[N];
vector<pair<int,int> >val[N],q[N];
void dfs1(int u,int fa)
{
dep[u]=dep[fa]+1;siz[u]=1;
f[u]=fa;
for(auto x:G[u])
{
if(x==fa) continue;
dfs1(x,u);
siz[u]+=siz[x];
if(siz[x]>siz[son[u]]) son[u]=x;
}
}
void dfs2(int u,int t)
{
top[u]=t;dfn[u]=++cnt;rev[cnt]=u;
if(son[u]) dfs2(son[u],t);
for(auto x:G[u])
{
if(x==f[u]||x==son[u]) continue;
dfs2(x,x);
}
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
int cmp(int x,int y){return dfn[x]<dfn[y];}
void Add(int s,int e){vec[s].push_back(e);vec[e].push_back(s);}
void build(int u)
{
sort(v[u].begin(),v[u].end(),cmp);
for(auto x:v[u])
{
tmp.push_back(x);
if(!tot)
{
s[++tot]=x;
continue;
}
int now=LCA(s[tot],x);
while(tot>1&&dep[s[tot-1]]>=dep[now]) Add(s[tot-1],s[tot]),tot--;
if(s[tot]!=now)
{
Add(s[tot],now);s[tot]=now;
tmp.push_back(now);
}
s[++tot]=x;
}
while(tot>1) Add(s[tot-1],s[tot]),tot--;
}
int check(int x,int y)
{
if(dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+siz[x]-1) return 1;
else return 0;
}
int find(int x,int y)
{
int pre=0;
while(top[x]^top[y])
{
pre=top[x];
x=f[top[x]];
}
if(x==y) return pre;
return rev[dfn[y]+1];
}
void modify(int a,int b,int c,int d)
{
if(a>b||c>d) return;
val[a].push_back(mp(c,1));val[a].push_back(mp(d+1,-1));
val[b+1].push_back(mp(c,-1));val[b+1].push_back(mp(d+1,1));
}
void add(int x,int y)
{
if(check(x,y))
{
int z=find(y,x);
modify(1,dfn[z]-1,dfn[y],dfn[y]+siz[y]-1);
modify(dfn[z]+siz[z],n,dfn[y],dfn[y]+siz[y]-1);
}
else if(check(y,x))
{
int z=find(x,y);
modify(dfn[x],dfn[x]+siz[x]-1,1,dfn[z]-1);
modify(dfn[x],dfn[x]+siz[x]-1,dfn[z]+siz[z],n);
}
else modify(dfn[x],dfn[x]+siz[x]-1,dfn[y],dfn[y]+siz[y]-1);
}
void dfs(int u,int pre,int s)
{
if(s<0) return;
for(auto x:vec[u])
{
if(x==pre) continue;
if(op[x]==2&&col[x]==z&&s==0)
{
add(now,x);
continue;
}
int d=0;
if(col[x]==z)
{
if(op[x]==1) d++;
else d--;
}
dfs(x,u,s+d);
}
}
int lowbit(int x){return x&(-x);}
void update(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val;
}
int query(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i)) sum+=c[i];
return sum;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
op[i]=read();col[i]=read();
v[col[i]].push_back(i);
}
for(int i=1;i<=n-1;i++)
{
A=read();B=read();
G[A].push_back(B);
G[B].push_back(A);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++)
{
if(!(int)v[i].size()) continue;
build(i);z=i;
for(auto x:v[i])
{
if(col[x]==i&&op[x]==1) now=x,dfs(x,0,0);
}
for(auto x:tmp) vec[x].clear();
tmp.clear();
tot=0;
}
for(int i=1;i<=m;i++)
{
A=read();B=read();
q[dfn[A]].push_back(mp(dfn[B],i));
}
for(int i=1;i<=n;i++)
{
for(auto x:val[i]) update(x.first,x.second);
for(auto x:q[i]) ans[x.second]=query(x.first);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
呱。