题解 CF375D 【Tree and Queries】
chenxinyang2006
·
·
题解
题解里貌似写的都是 DSU on tree 或者莫队的做法，这里介绍一个线段树合并，时间复杂度为 O(n \log n + m \log n) 的做法
对于 u 节点的子树，维护两颗线段树 T1_u,T2_u，T1_u 下标 i 对应的值表示颜色为 i 的点在子树 u 内的个数，T2_u 下标 i 对应的值表示有多少颜色出现次数为 i
现在考虑如何从 u 的子节点 v_1,v_2...v_k 转移到 u
T1_u$ 的值实际上就是将所有 $T1_{v_1},T1_{v_2}...T1_{v_k}$ 进行线段树合并后，再在 $c_u$ 的位置加上 $1
对于一种颜色 $col$，我们可以进行两类分类
- 在子树 $u$ 中，颜色为 $col$ 的点都属于 $u$ 的一个儿子 $v$ 的子树
对于这类情况，在子树 $u$ 中 $col$ 的出现次数与在子树 $v$ 中是相同的，对于这类情况，实际上我们可以对于 $T2$ 也进行线段树合并
- 在子树 $u$ 中，颜色为 $col$ 的点属于 $u$ 的多个儿子 $v_1,v_2..v_k$ 的子树
对于这类情况，我们就只能暴力修改 $T2$ 了
那么实际上现在的问题就是如何快速找出哪些颜色是情况一，哪些颜色是情况二
实际上我们可以在 $T1$ 进行线段树合并时，找到所有被合并的叶子节点并记录它们对应的颜色，这样就找出了所有的情况二
由线段树合并的复杂度分析我们可以知道，情况二最多只会出现 $O(n)$ 次，所以暴力修改的复杂度是对的
那么该如何只对所有情况一的颜色进行线段树合并呢？
答案是把所有情况都装作是情况一，然后对于情况二的颜色，删去各个子树 $v$ 内颜色的出现次数，加入子树 $u$ 内颜色的出现次数
这里可能有一点细节问题，就是如何求出所有含有这种颜色的子树 $v$ 内的出现次数
也是在线段树合并到叶节点时特判一下，放到一个 `vector` 里
但是这些部分我们都没有讨论 $u$ 节点的颜色该如何处理
其实也比较简单，只要把 $u$ 节点的颜色当作是它自己一个特殊的子节点的颜色就行了
对于查询，其实就是在 $T2$ 上进行一下区间求和，如果追求在线算法的话可以选择可持久化线段树合并，但是我懒得写了，就写了离线算法
code：
```cpp
#include <cstdio>
#include <vector>
using namespace std;
int n,m;
int a[100005];
int cnt;
int head[100005];
struct eg{
int to,nxt;
}edge[200005];
void make(int u,int v){
edge[++cnt].to = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int T1[100005],T2[100005];
struct node{
int val,l,r;
}tree[5000005];
int tag[100005];
#define ls(x) tree[x].l
#define rs(x) tree[x].r
void fx(int &x){
if(x == 0){
x = ++cnt;
tree[x].val = ls(x) = rs(x) = 0;
}
}
vector <int> S,T;
void upload(int rt,int l,int r,int id,int C){
tree[rt].val += C;
if(l == r) return;
int mid = l + r >> 1;
if(id <= mid){
fx(ls(rt));
upload(ls(rt),l,mid,id,C);
}else{
fx(rs(rt));
upload(rs(rt),mid+1,r,id,C);
}
}
int query(int rt,int l,int r,int L,int R){
if(!rt) return 0;
if(l == L && r == R) return tree[rt].val;
int mid = l + r >> 1;
if(R <= mid) return query(ls(rt),l,mid,L,R);
else if(L > mid) return query(rs(rt),mid+1,r,L,R);
else return query(ls(rt),l,mid,L,mid) + query(rs(rt),mid+1,r,mid+1,R);
}
int Merge(int x,int y,int l,int r){
if(!x || !y) return x + y;
if(l == r){
if(!tag[l] && tree[x].val > 0){
tag[l] = 1;
S.push_back(l);
T.push_back(tree[x].val);
}
if(tree[y].val > 0) T.push_back(tree[y].val);
}
tree[x].val += tree[y].val;
int mid = l + r >> 1;
ls(x) = Merge(ls(x),ls(y),l,mid);
rs(x) = Merge(rs(x),rs(y),mid+1,r);
return x;
}
int res[100005];
struct ask{
int k,id;
};
vector <ask> Q[100005];
void dfs(int now,int fa){
for(int i = head[now];i;i = edge[i].nxt){
if(edge[i].to == fa) continue;
dfs(edge[i].to,now);
}
S.clear();
T.clear();
fx(T1[now]);
upload(T1[now],1,100000,a[now],1);
for(int i = head[now];i;i = edge[i].nxt){
if(edge[i].to == fa) continue;
T1[now] = Merge(T1[now],T1[edge[i].to],1,100000);
}
fx(T2[now]);
upload(T2[now],1,100000,1,1);
for(int i = 0;i < T.size();i++) upload(T2[now],1,100000,T[i],-1);
for(int i = 0;i < S.size();i++) upload(T2[now],1,100000,query(T1[now],1,100000,S[i],S[i]),1);
for(int i = head[now];i;i = edge[i].nxt){
if(edge[i].to == fa) continue;
T2[now] = Merge(T2[now],T2[edge[i].to],1,100000);
}
for(int i = 0;i < S.size();i++) tag[S[i]] = 0;
for(int i = 0;i < Q[now].size();i++) res[Q[now][i].id] = query(T2[now],1,100000,Q[now][i].k,100000);
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i < n;i++){
int u,v;
scanf("%d%d",&u,&v);
make(u,v);make(v,u);
}
for(int i = 1;i <= m;i++){
int u,k;
scanf("%d%d",&u,&k);
Q[u].push_back({k,i});
}
cnt = 0;
dfs(1,0);
for(int i = 1;i <= m;i++) printf("%d\n",res[i]);
return 0;
}
```