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

#图论 #数据结构 #异或 #启发式合并

Published on 2016-12-07

题目地址

描述

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

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

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

分析

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

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

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

如果我们考虑启发式合并，对于节点 $u$ ，最后递归计算其最大的子树，并从最大的子树中继承 $h$ ，这样在更新答案的时候就只需要遍历其余的子树。不难发现每一个点只会被遍历 $O(\log n)$ 次（每次遍历到一个点，其所在子树大小必然翻倍），所以总的时间复杂度降为： $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;
}

BZOJ 3811 - 玛里苟斯 Codeforces 735E - Ostap and Tree

Sengxian's Blog

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

描述

分析

代码