Description
给一棵树,无修改操作,每次查询给出 (l,r),查询 l 的子树在深度为 r 的节点对应的字母能不能构成回文串。
Solution
思路:dsu on tree(树上启发式合并)
算法的本质其实就是一个优化暴力的过程。按暴力的想法去统计,每次统计所有子树,再删除贡献,时间复杂度是 的。但是在dsu on tree的思想中,我们先进行轻重链剖分,只暴力统计并删除轻儿子,对于重儿子只统计不删除,有效地优化了暴力过程,能将时间复杂度降为
具体的算法步骤是:
1.暴力统计每个轻儿子(注意,每个轻儿子统计完后要删掉贡献)
2.统计重儿子
3.再重新暴力统计轻儿子,与重儿子的贡献合并提供给根节点
4.删除轻儿子的贡献。
在这题中需要得到回文串,关键条件在于出现奇数次的字母不能超过一个及以上,否则构不成回文串。令 表示深度为 u 时,字母i的出现次数,离线查询即可。
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e5 + 5; vector<int> G[N]; vector<pair<int, int> > V[N]; int son[N], sz[N], dep[N], s1[N], ans[N]; int cnt[N][30], Son; void dfs1(int u, int par) { // 第一遍dfs, 轻重链剖分 sz[u] = 1; int maxz = 0; for(auto &x : G[u]) { if(x == par) continue; dep[x] = dep[u] + 1; dfs1(x, u); sz[u] += sz[x]; if(sz[x] > maxz) { // 找重儿子 maxz = sz[x]; son[u] = x; } } } void update(int u, int val) { // 进行修改 cnt[dep[u]][s1[u]] += val; for(auto &x : G[u]) { if(x != Son) { // 不是重儿子的都统计下来 update(x, val); } } } void dsu(int u, int f) { for(auto &x : G[u]) { // 先统计轻儿子 if(x == son[u]) continue; dsu(x, 0); } if(son[u]) { // 统计重儿子 dsu(son[u], 1); Son = son[u]; } update(u, 1); for(auto &x : V[u]) { // 对于当前点u的每个相关查询进行统计 int tmp = 0, flag = 0; for(int j = 1; j <= 26; j++) { if(cnt[x.first][j] & 1) { // 统计奇数个的字母 tmp++; } if(tmp >= 2) { // 奇数超过俩就不行 ans[x.second] = 0; flag = 1; } } if(!flag) { ans[x.second] = 1; } } if(son[u]) Son = 0; if(!f) update(u, -1); // 消除贡献 } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int n, m; cin >> n >> m; for(int i = 2; i <= n; i++) { int x; cin >> x; G[x].push_back(i); } dep[1] = 1; string s; cin >> s; s = ' ' + s; for(int i = 1; i <= n; i++) { s1[i] = s[i] - 'a' + 1; } dfs1(1, 0); for(int i = 1; i <= m; i++) { int x, h; cin >> x >> h; V[x].push_back(make_pair(h, i)); } dsu(1, 1); for(int i = 1; i <= m; i++) { string output = ans[i] ? "Yes\n" : "No\n"; cout << output; } return 0; }