题意：
给出一棵树，1是根节点，n个节点，每个节点有一种颜色。
有m次询问，每次询问给出v k，求以v节点为根的子树中有多少种数量至少为k的颜色，一种颜色的数量就是该颜色的节点的数量。
题解：
离线，回答以v为根的询问时，如果暴力把整棵子树的颜色存进树状数组，复杂度是 O(n2logn) 。
但是子树信息可以保留到父节点继续使用，如果要保留子树信息的话，容易发现处理两棵子树时，子树间会相互影响，所以先不保留地处理较小的子树，最后保留地处理最大子树。
用树链剖分的思想来说，我们应该保留重儿子的信息，可以证明这样复杂度是 O(nlognlogn) 。
这种方法对于一类子树上的查询问题有时候还是比较好用的，但是我还不知道中文名叫什么，这个文章讲的十分清楚了，例题也十分精髓。
#include
using namespace std;
const int N = 1e5+5;
typedef pair pii;
vectorG[N];
int val[N];
int tree[N];
void update(int p, int v){
for(p = N-p-1;
p < N;
p += p&-p) tree[p] += v;
}
int getsum(int p){
int res = 0;
for(p = N-p-1;
p;
p -= p&-p) res += tree[p];
return res;
}
int sz[N];
void predfs(int rt, int f){
sz[rt] = 1;
for(auto& v : G[rt]){
if(v != f) predfs(v, rt), sz[rt] += sz[v];
}
}
vector【ACM|[dsu] codeforces 375D. Tree and Queries】query[N];
bool bg[N];
int ans[N], col[N];
void add(int rt, int f, int x){
update(col[val[rt]], -1);
col[val[rt]] += x;
update(col[val[rt]], 1);
for(auto& v : G[rt]){
if(v != f && !bg[v]) add(v, rt, x);
}
}
void dfs(int rt, int f, int kp){
int mx = -1, u = -1;
for(auto& v : G[rt]){
if(v != f && sz[v] > mx) mx = sz[v], u = v;
}
if(u != -1) bg[u] = 1;
for(auto& v : G[rt]){
if(v != f && !bg[v]) dfs(v, rt, 0);
}
if(u != -1) dfs(u, rt, 1);
add(rt, f, 1);
for(auto& x : query[rt]) ans[x.first] = getsum(x.second);
if(u != -1) bg[u] = 0;
if(!kp) add(rt, f, -1);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1;
i <= n;
++i) scanf("%d", val+i);
for(int i = 1;
i < n;
++i){
int a, b;
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
predfs(1, -1);
for(int i = 1;
i <= m;
++i){
int v, k;
scanf("%d%d", &v, &k);
query[v].push_back(pii(i, k));
}
dfs(1, -1, 0);
for(int i = 1;
i <= m;
++i) printf("%d\n", ans[i]);
} 推荐阅读
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- 牛客算法周周练15——A、B
- Codeforces Round #609 (Div. 2)——C. Long Beautiful Integer（思维）
- 题解|【HNOI2017】大佬-dalao
- FZU - 2107题解
- 2019 GDUT Rating Contest #II 这是群题解，七篇！！！
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth
- 2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解