强大的解决对于子树的询问问题。
有个英文名字叫 dsu on tree。
一种是基于重链剖分的，一种是基于set map的启发式合并的。
第一种就是先走轻边，再走重边，重边的不改回来，这样修改次数就是 $logn$ 次的。
第二种就是看set map的size，把size小的并到大的上。
模板题啦
#include <bits/stdc++.h> #define ll long long const int N = 1e5 + 7; int n, cc[N], col[N], son[N], sz[N], skip[N]; ll ans[N]; std::vector<int> G[N]; void dfs1(int u, int fa = 0) { sz[u] = 1; for (auto v: G[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } ll sum; int cx; void edt(int u, int fa, int k) { cc[col[u]] += k; if (k > 0 && cc[col[u]] >= cx) { if (cc[col[u]] > cx) sum = 0, cx = cc[col[u]]; sum += col[u]; } for (auto v: G[u]) if (v != fa && !skip[v]) edt(v, u, k); } void dfs(int u, int fa = 0, bool kep = 0) { for (auto v: G[u]) if (v != fa && v != son[u]) dfs(v, u); if (son[u]) dfs(son[u], u, 1), skip[son[u]] = 1; edt(u, fa, 1); ans[u] = sum; if (son[u]) skip[son[u]] = 0; if (!kep) edt(u, fa, -1), cx = sum = 0; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", col + i); for (int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs1(1); dfs(1); for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " \n"[i == n]); return 0; }
把询问离线，一些字母能组成回文串，即出现偶数次的字母不能超过一个，那么对每一个深度用一个26位的二进制数表示一个字母出现的奇偶性，记为 $cnt[dep]$ 即可。
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second const int N = 5e5 + 7; std::vector<int> G[N]; std::vector<std::pii> que[N]; int cnt[N], n, m, dep[N], sz[N], son[N]; char s[N]; bool ans[N], skip[N]; void dfs1(int u, int d) { dep[u] = d; sz[u] = 1; for (auto v: G[u]) { dfs1(v, d + 1); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void edt(int u) { cnt[dep[u]] ^= (1 << (s[u] - ‘a‘)); for (auto v: G[u]) if (!skip[v]) edt(v); } bool check(int d) { int res = 0; for (int i = 0; i < 26; i++) if (cnt[d] >> i & 1) res++; return res <= 1; } void dfs(int u, int keep = 0) { for (auto v: G[u]) if (v != son[u]) dfs(v, 0); if (son[u]) dfs(son[u], 1), skip[son[u]] = 1; edt(u); for (auto p: que[u]) ans[p.se] = check(p.fi); if (son[u]) skip[son[u]] = 0; if (!keep) edt(u); } int main() { // freopen("in.txt", "r", stdin); scanf("%d%d", &n, &m); for (int i = 2; i <= n; i++) { int x; scanf("%d", &x); G[x].push_back(i); } scanf("%s", s + 1); for (int i = 1, u, h; i <= m; i++) { scanf("%d%d", &u, &h); que[u].push_back(std::pii(h, i)); } dfs1(1, 1); dfs(1); for (int i = 1; i <= m; i++) puts(ans[i] ? "Yes" : "No"); return 0; }
想用重链剖分的写法。用一个multiset维护出现的数字，一个multiset维护每个插入的数和附近两个数的差值.
但是这跟插入顺序有关，插入的时候正着插入，删除的时候倒着删除，然后WA on 20了... 正着删除有RE on 20了...
看了一下别人的解法就是，每个结点维护一个set，发现这个set元素个数最多是所有叶子个数，空间能接受，然后就启发式合并就OK了。
#include <bits/stdc++.h> namespace IO { void read() {} template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { T f = 1; x = 0; char ch = getchar(); while (!isdigit(ch)) { if (ch == ‘-‘) f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; read(oth...); } } // using namespace IO #define read IO::read #define print IO::print #define flush IO::flush const int N = 1e5 + 7; const int INF = 2147483647; std::vector<int> vec[N]; std::set<int> st[N]; int n, m, color[N], ans[N]; int merge(int u, int v) { if (st[u].size() < st[v].size()) std::swap(st[u], st[v]); int res = INF; for (std::set<int>::iterator it = st[v].begin(); it != st[v].end(); it++) { auto i = st[u].lower_bound(*it); if (i == st[u].begin()) { res = std::min(res, *i - *it); } else if (i == st[u].end()) { i--; res = std::min(res, *it - *i); } else { res = std::min(res, *i - *it); i--; res = std::min(res, *it - *i); } st[u].insert(*it); } st[v].clear(); return res; } void dfs(int u) { ans[u] = INF; if (vec[u].size() == 0) { st[u].insert(color[u]); return; } for (int v: vec[u]) { dfs(v); ans[u] = std::min(ans[u], ans[v]); ans[u] = std::min(ans[u], merge(u, v)); } } int main() { read(n, m); for (int i = 2; i <= n; i++) { int u; read(u); vec[u].push_back(i); } for (int i = n - m + 1; i <= n; i++) read(color[i]); dfs(1); for (int i = 1; i <= n - m; i++) printf("%d%c", ans[i], " \n"[i == n - m]); return 0; }
这个就是每个结点维护一个map表示其子树钟出现过的数字以及出现的次数。
然后根据合并前枚举小的map里面的每个元素，看看大的map中能与其相乘成为当前结点的值的就行了。
#include <bits/stdc++.h> #define ll long long const int N = 1e5 + 7; std::map<int, int> mp[N]; int n, val[N]; std::vector<int> vec[N]; ll ans; void merge(int u, int v) { if (mp[u].size() < mp[v].size()) std::swap(mp[u], mp[v]); for (auto p: mp[v]) { if (val[u] % p.first == 0) ans += 1LL * p.second * mp[u][val[u] / p.first]; } for (auto p: mp[v]) mp[u][p.first] += p.second; mp[v].clear(); } void dfs(int u, int fa) { mp[u][val[u]] = 1; for (int v: vec[u]) { if (v == fa) continue; dfs(v, u); merge(u, v); } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } for (int i = 1; i <= n; i++) scanf("%d", val + i); dfs(1, 0); printf("%lld\n", ans); return 0; }
对每一个深度用一个map维护出现的字符串以及出现的次数，然后然后就做完了。
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second const int N = 1e5 + 7; char s[N][22]; std::vector<int> vec[N]; std::vector<std::pii> query[N]; std::map<std::string, int> mp[N]; int n, son[N], sz[N], dep[N], ans[N], root, cnt[N]; bool skip[N]; void dfs1(int u, int d) { sz[u] = 1; dep[u] = d; son[u] = -1; for (int v: vec[u]) { dfs1(v, d + 1); sz[u] += sz[v]; if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v; } } void edt(int u, int k) { mp[dep[u]][s[u]] += k; int w = mp[dep[u]][s[u]]; if (k == 1 && w == 1) cnt[dep[u]]++; if (k == -1 && w == 0) cnt[dep[u]]--; assert(cnt[dep[u]] >= 0); for (int v: vec[u]) if (!skip[v]) edt(v, k); } void dfs(int u, bool keep = 0) { for (int v: vec[u]) if (v != son[u]) dfs(v); if (son[u] != -1) dfs(son[u], 1), skip[son[u]] = 1; edt(u, 1); for (auto p: query[u]) ans[p.se] = cnt[dep[u] + p.fi]; if (son[u] != -1) skip[son[u]] = 0; if (!keep) edt(u, -1); } int main() { scanf("%d", &n); for (int i = 1, u; i <= n; i++) { scanf("%s%d", s[i], &u); vec[u].push_back(i); } int m; scanf("%d", &m); for (int i = 1; i <= m; i++) { int u, k; scanf("%d%d", &u, &k); query[u].push_back(std::pii(k, i)); } dfs1(0, 0); dfs(0, 1); for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }
先转换一下询问，把 $v_i$ 往上跳 $p_i$ 步得到 $u_i$，变成询问 $u_i$ 有多少个 $p_i$ 级儿子。然后就做完了。
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second const int N = 1e5 + 7; int dep[N], son[N], sz[N], n, fa[N][20], ans[N]; bool skip[N]; std::vector<int> vec[N]; std::vector<std::pii> query[N]; void dfs1(int u, int pre = 0, int d = 0) { dep[u] = d; fa[u][0] = pre; for (int i = 1; i <= 18; i++) { fa[u][i] = fa[fa[u][i - 1]][i - 1]; if (!fa[u][i]) break; } sz[u] = 1; son[u] = -1; for (int v: vec[u]) { dfs1(v, u, d + 1); sz[u] += sz[v]; if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v; } } int jump(int u, int k) { for (int i = 18; ~i; i--) if (k >> i & 1) u = fa[u][i]; return u; } int cnt[N]; void edt(int u, int k) { cnt[dep[u]] += k; for (int v: vec[u]) if (!skip[v]) edt(v, k); } void dfs(int u, bool keep = 0) { for (int v: vec[u]) if (v != son[u]) dfs(v); if (son[u] != -1) dfs(son[u], 1), skip[son[u]] = 1; edt(u, 1); for (auto p: query[u]) { ans[p.se] = cnt[dep[u] + p.fi] - 1; } if (son[u] != -1) skip[son[u]] = 0; if (!keep) edt(u, -1); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int u; scanf("%d", &u); vec[u].push_back(i); } int m; scanf("%d", &m); dfs1(0); for (int i = 1; i <= m; i++) { int u, k; scanf("%d%d", &u, &k); u = jump(u, k); if (u) query[u].push_back(std::pii(k, i)); } dfs(0, 1); for (int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]); return 0; }
待续...
原文：https://www.cnblogs.com/Mrzdtz220/p/11723663.html
