Codeforces 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

Published on 2016-12-07

题目地址

描述

给定一棵 n(1n5105)n(1\le n\le 5 \cdot {10}^5) 的有根树,根结点为 11,每条边上写有一个字母

对于一个字符串,如果我们将字符串中的字母排列后能够得到一个回文串,那么就称这个字符串是是 Dokhtar-kos 串。

请问对于每一个点 vv,其子树中最长的满足路径上所有边上的字母能形成一个 Dokhtar-kos 串的路径长度是多少?

分析

我们考虑用状态压缩来记录路径上字母的信息,设 d(i)d(i) 为点 ii 到根的路径上字母的信息。则 d(i)d(i) 中第 ii 位为 ii 当且仅当第 ii 个字母在 ii 到根的路径上出现了奇数次。

对于一条路径 (u,v)(u, v),其路径上字母的信息为 d(u)d(v)d(u) \oplus d(v)。这一条路径满足条件当且仅当 d(u)d(v)d(u) \oplus d(v) 的二进制位中有不超过 1 位为 11。如果我们考虑对于 d(u)d(u),有多少种 d(v)d(v) 能够满足条件,不难发现只有 22+122 + 1 种(因为 d(v)d(v) 至多只能有 1 位与 d(u)d(u) 不同)。

于是利用这一性质,我们就可以利用 d(u)d(u) 来快速更新答案。对于每一个节点 uu,首先递归计算其子树,再考虑用 LCA 为 uu 的路径更新答案。维护 h(i)h(i)d(u)=id(u) = i 中最大的 dep(u)\mathrm{dep(u)}。顺序遍历其子树,每次先用子树中的点 vv 来更新答案 dep(v)+hd(v)x2dep(u)\mathrm{dep}(v) + h_{d(v) \oplus x} - 2 \cdot \mathrm{dep}(u),其中 x=0x = 0 或者 ,更新完答案后再用这棵子树中的点来更新 hh。由于每一次都需要遍历所有的子树,时间复杂度为 O(n2)O(n^2)

如果我们考虑启发式合并,对于节点 uu,最后递归计算其最大的子树,并从最大的子树中继承 hh,这样在更新答案的时候就只需要遍历其余的子树。不难发现每一个点只会被遍历 O(logn)O(\log n) 次(每次遍历到一个点,其所在子树大小必然翻倍),所以总的时间复杂度降为:O(nlogn22)O(n\log n \cdot 22)

代码

//  Created by Sengxian on 2016/12/07.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 741D 启发式合并
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 500000 + 3, MAX_CHAR = 22;
struct edge {
    edge *next;
    int to, val;
    edge(edge *next = NULL, int to = 0, int val = 0): next(next), to(to), val(val) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];
int n, ans[MAX_N], h[1 << MAX_CHAR];

int s[MAX_N], dep[MAX_N], d[MAX_N], dfn[MAX_N], seq[MAX_N];
void dfs(int u, int fa) {
    static int tsp = 0;
    s[u] = 1, dfn[u] = tsp, seq[tsp++] = u;
    for (edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        dep[e->to] = dep[u] + 1;
        d[e->to] = d[u] ^ e->val;
        dfs(e->to, u);
        s[u] += s[e->to];
    }
}

void update(int u, int root) {
    ans[root] = max(ans[root], dep[u] + h[d[u]] - 2 * dep[root]);
    for (int i = 0; i < MAX_CHAR; ++i)
        ans[root] = max(ans[root], dep[u] + h[d[u] ^ (1 << i)] - 2 * dep[root]);
}

void add(int u) {
    h[d[u]] = max(h[d[u]], dep[u]);
}

void remove(int u, int fa) {
    h[d[u]] = -0x3f3f3f3f;
    for (edge *e = first[u]; e; e = e->next) if (e->to != fa)
        remove(e->to, u);
}

void dfs(int u, int fa, bool keep) {
    int mx = 0, id = -1;
    for (edge *e = first[u]; e; e = e->next)
        if (e->to != fa && s[e->to] > mx)
            mx = s[id = e->to];

    for (edge *e = first[u]; e; e = e->next)
        if (e->to != fa && e->to != id)
            dfs(e->to, u, false);

    if (id != -1) dfs(id, u, true), ans[u] = ans[id];

    for (edge *e = first[u]; e; e = e->next)
        if (e->to != fa && e->to != id) {
            ans[u] = max(ans[u], ans[e->to]);

            for (int i = dfn[e->to]; i < dfn[e->to] + s[e->to]; ++i)
                update(seq[i], u);

            for (int i = dfn[e->to]; i < dfn[e->to] + s[e->to]; ++i)
                add(seq[i]);
        }

    update(u, u), add(u);

    if (!keep) remove(u, fa);
}

int main() {
    n = readInt();
    for (int u = 1; u < n; ++u) {
        int v = readInt() - 1, ch = getchar() - 'a';
        first[u] = new (pit++) edge(first[u], v, 1 << ch);
        first[v] = new (pit++) edge(first[v], u, 1 << ch);
    }

    memset(h, -0x3f, sizeof h);
    dfs(0, -1);
    dfs(0, -1, 0);

    for (int i = 0; i < n; ++i) printf("%d%c", ans[i], i + 1 == n ? '\n' : ' ');
    return 0;
}