题意
题目链接
给出一棵 n 个结点的树,每个结点有一个颜色 c i 。 询问 q 次,每次询问以 v 结点为根的子树中,出现次数 ≥k 的颜色有多少种。树的根节点是1。
sol
想到了主席树和启发式合并。。很显然都不能做。
标算是dfs序上暴力莫队。。甘拜下风
具体实现的时候可以直接用(tim[i])表示第(i)个颜色的出现次数,(ans[i])表示出现次数多于(i)的颜色的种类
由于左右端点移动的时候只会对一个(ans[i])产生影响,所以修改是(o(1))的
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, dfn[maxn], rev[maxn], tot, block, bel[maxn], siz[maxn], col[maxn], tims[maxn], ans[maxn], out[maxn]; vector<int> v[maxn]; struct query{ int id, l, r, k; bool operator < (const query &rhs) const { return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l]; } }q[maxn]; void dfs(int x, int fa) { dfn[x] = ++tot; rev[tot] = x; siz[x] = 1; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa) continue; dfs(to, x); siz[x] += siz[to]; } } void add(int x, int opt) { if(opt == 1) ans[++tims[x]]++; else ans[tims[x]--]--; } void solve() { sort(q + 1, q + m + 1); int l = 1, r = 0; for(int i = 1; i <= m; i++) { while(r > q[i].r) add(col[rev[r--]], -1); while(r < q[i].r) add(col[rev[++r]], 1); while(l < q[i].l) add(col[rev[l++]], -1); while(l > q[i].l) add(col[rev[--l]], 1); out[q[i].id] = ans[q[i].k]; ///printf("%dn", out[q[i].id]); } for(int i = 1; i <= m; i++) printf("%dn", out[i]); } int main() { n = read(); m = read(); block = sqrt(n); for(int i = 1; i <= n; i++) col[i] = read(), bel[i] = (i - 1) / block + 1; for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); for(int i = 1; i <= m; i++) { q[i].id = i; int x = read(); q[i].k = read(); q[i].l = dfn[x]; q[i].r = dfn[x] + siz[x] -1; } solve(); return 0; } /* */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606903.html