570D - Tree Requests

题意

给出一棵树，每个节点上有字母，查询 u k，问以 u 为根节点的子树下，深度为 k 的所有子节点上的字母经过任意排列是否能构成回文串。

分析

一个数组 \(C[i][j]\) 表示深度为 \(i\) 字母为 \(j\) 的数量，数组 \(odd[i]\) 表示深度为 \(i\) 时出现次数为奇数的字母种数。

如果想要构成回文串，那么某一深度下出现的次数为奇数的字母不能超过一种，注意如果字符串长度为 0 也叫回文串。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int n;

int fa[MAXN], son[MAXN], dep[MAXN], siz[MAXN];

int col[MAXN];

int cnt, head[MAXN];

struct Edge {

    int to, next;

} e[MAXN << 1];

struct Ex {

    int x, c;

};

vector<Ex> ex[MAXN];

void addedge(int u, int v) {

    e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++;

    e[cnt].to = u; e[cnt].next = head[v]; head[v] = cnt++;

}

void dfs(int u) {

    siz[u] = 1;

    son[u] = 0;

    for(int i = head[u]; ~i; i = e[i].next) {

        if(e[i].to != fa[u]) {

            fa[e[i].to] = u;

            dep[e[i].to] = dep[u] + 1;

            dfs(e[i].to);

            if(siz[e[i].to] > siz[son[u]]) son[u] = e[i].to;

            siz[u] += siz[e[i].to];

        }

    }

}

int vis[MAXN], ans[MAXN];

int mk[MAXN];

int C[MAXN][30], odd[MAXN], num[MAXN];

void change(int u, int c) {

    C[dep[u]][mk[u]] += c;

    num[dep[u]] += c;

    if(C[dep[u]][mk[u]] & 1) odd[dep[u]]++;

    else odd[dep[u]]--;

    for(int i = head[u]; ~i; i = e[i].next) {

        if(e[i].to != fa[u] && !vis[e[i].to]) change(e[i].to, c);

    }

}

void dfs1(int u, int flg) {

    for(int i = head[u]; ~i; i = e[i].next) {

        if(e[i].to != fa[u] && e[i].to != son[u]) dfs1(e[i].to, 1);

    }

    if(son[u]) {

        dfs1(son[u], 0);

        vis[son[u]] = 1;

    }

    change(u, 1);

    int sz = ex[u].size();

    for(int i = 0; i < sz; i++) {

        ans[ex[u][i].x] = (odd[ex[u][i].c] <= 1 || num[ex[u][i].c] == 0);

    }

    if(son[u]) vis[son[u]] = 0;

    if(flg) change(u, -1);

}

char ss[MAXN];

int main() {

    int m;

    scanf("%d%d", &n, &m);

    memset(head, -1, sizeof head);

    cnt = 0;

    dep[1] = 1;

    for(int i = 2; i <= n; i++) {

        int x;

        scanf("%d", &x);

        addedge(i, x);

    }

    scanf("%s", ss);

    for(int i = 0; i < n; i++) {

        mk[i + 1] = ss[i] - 'a';

    }

    dfs(1);

    for(int i = 0; i < m; i++) {

        int x, y;

        scanf("%d%d", &x, &y);

        ex[x].push_back(Ex{i, y});

    }

    dfs1(1, 0);

    for(int i = 0; i < m; i++) {

        puts(ans[i] ? "Yes" : "No");

    }

    return 0;

}