【树上启发式合并】Codeforces 570 D.Tree Requests

D.Tree Requests

题目链接

给出一棵树，每个节点都有一个字母，现在有 m 个询问，每个询问给出两个值 : u,dep。
u 的子树中深度为 dep 的所有字母，全部使用，可以以任意顺序排列是否可以构成一个回文串。

判断是否可以构成回文串不难，只要 26 个字母中在那一层出现的次数为奇数的少于 2 个就可以。

关键是如何统计某子树中某深度所有 26 个字母的出现次数。

我之前想的是维护一个怎样的神奇的数组，读入一个查询，直接输出，但是怎么想都维护不了。

看题解发现，因为没有修改，可以离线查询，所以我们可以将查询存起来，在 \(dfs\) 的过程中求解每个查询。

因为对于某颗子树维护某个深度26个字母出现的次数很简单，加上启发式合并即可。

代码

#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;

vector<int> vec[N];
int val[N], son[N], sz[N];
void dfs1(int u, int fa)
{
    sz[u] = 1;
    for (auto v : vec[u]) {
        if (v == fa)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]])
            son[u] = v;
    }
}
int cnt[N][30];
vector<pair<int, int>> q[N];
char str[N];
void cal(int u, int type, int dep)
{
    cnt[dep][str[u] - 'a'] += type;
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        cal(v, type, dep + 1);
    }
}
struct note {
    int u, v, ans;
} arr[N];
void dfs2(int u, int type, int dep)
{
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (v != son[u])
            dfs2(v, -1, dep + 1);
    }
    if (son[u])
        dfs2(son[u], 1, dep + 1);
    cnt[dep][str[u] - 'a']++;
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (v != son[u])
            cal(v, 1, dep + 1);
    }
    for (int i = 0; i < q[u].size(); i++) {
        int dis = q[u][i].first, id = q[u][i].second, num = 0;
        for (int j = 0; j < 26; j++) {
            if (cnt[dis][j] % 2)
                num++;
        }
        if (num <= 1) {
            arr[id].ans = 1;
        } else {
            arr[id].ans = 0;
        }
    }
    if (type == -1)
        cal(u, -1, dep);
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++) {
        int fa;
        scanf("%d", &fa);
        vec[fa].pb(i);
    }
    scanf("%s", str + 1);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &arr[i].u, &arr[i].v);
        q[arr[i].u].pb({ arr[i].v, i });
    }
    dfs1(1, 0);
    dfs2(1, 1, 1);
    for (int i = 1; i <= m; i++) {
        if (arr[i].ans) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}