锐客网

  1. 首页 > it技术 > >

ACM|[dsu] codeforces 375D. Tree and Queries

ACM题解

题意：
给出一棵树，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]); }

    推荐阅读


    上一篇：Android事件分发拦截机制(图解)

    下一篇：MSXML2.XMLHTTP.4.0对象