题解：P9648 [SNCPC2019] Unrooted Trie

简化题意

求有多少个点，满足以它为根的时候 trie 合法。

1\le \sum n\le 10^6

思路

先思考什么样的 trie 是非法的。

非法的定义：存在一对不同的点代表的字符串相同，则 trie 非法。

那么 trie 非法，必定存在一个点连向儿子的边中有一对边上的字符相同（以下简称相同）。

我们先暂定

1

为根。为了方便，以下称“当下”指在以

1

为根的树中。

当我们在遍历树的时候，如果遇到一个点

u

连出的边中有相同时：

相同的边不少于 $3$ 条：这无论如何怎么选根，这个点必定有两个连向儿子的相同的边。直接退出输出 $0$ 。
那么接下来只有一对边相同。当下两边均连向儿子：我们只能选择两儿子的子树中的点为根，不然两儿子必定仍然是这个节点的儿子。
当下一条边连向父亲，一条边连向儿子 $v$ ：选择 $u$ 的子树外的点或 $v$ 的子树。理由同上。

至此，我们能在遍历树的时候就能判定每个点一定非法。遍历结束以后就能够知道有哪些点合法了。

令

s_i

表示点

i

为根是合法的。很明显，暴力修改

s

直接超时，我们使用树上差分，初始

s_1

为

1

。

上面的情况 1：

s_1\leftarrow s_1-1,s_{v1}\leftarrow s_{v1}+1,s_{v2}\leftarrow s_{v2}+1

，

s_{v1},s_{v2}

表示两儿子。

情况 2：

s_u\leftarrow s_u-1,s_v\leftarrow s_v+1

。

每个询问时间复杂度

\mathcal{O}(n)

。

上代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, M = 30;

int n, m, tot[M], op, s[N], t[M];
// s 如上，t_i 记录边为 i 的儿子，tot_i 记录个数

struct Edge {
    int to, next, w;
} e[N << 1];
int p, h[N];
void add(int u, int v, int w) {
    e[++ p] = {v, h[u], w};
    h[u] = p;
} // 链式前向星

void dfs1(int u, int pre) {
    if (!op) return;

    memset(tot, 0, sizeof tot);
    memset(t, 0, sizeof t); // 勿忘清空

    for (int i = h[u];i;i = e[i].next) {
        int v = e[i].to; 
        tot[e[i].w] ++; // 计数

        if (tot[e[i].w] > 2) {op = 0; return;}

        if (tot[e[i].w] == 2) {
            if (v == pre || t[e[i].w] == pre) {
                s[u] --;
                if (v == pre) s[t[e[i].w]] ++;
                else s[v] ++;
            }
            else {
                s[1] --; s[v] ++;
                s[t[e[i].w]] ++;
            } // 树上差分
        }
        else t[e[i].w] = v;
    }
    for (int i = h[u];i;i = e[i].next) {
        int v = e[i].to;
        if (v == pre) continue;
        dfs1(v, u);
    }
}
void dfs2(int u, int pre) {
    for (int i = h[u];i;i = e[i].next) {
        int v = e[i].to;
        if (v == pre) continue;
        s[v] += s[u];
        dfs2(v, u);
    }
} 
void solve() {
    memset(s, 0, sizeof s); // 勿忘清空
    op = 1; memset(h, 0, sizeof h); p = 0;

    cin >> n; int x, y; char ch;
    for (int i = 1;i < n;i ++) {
        cin >> x >> y, cin >> ch;
        add(x, y, ch - 'a' + 1);
        add(y, x, ch - 'a' + 1);
    } // 读入

    dfs1(1, 0);
    if (!op) return cout << "0\n", void(0);
    dfs2(1, 0); // 遍历

    int ans = 0; // 记录答案
    for (int i = 1;i <= n;i ++)
        if (s[i] >= 0) ans ++; 
    cout << ans << "\n";
}
int main() {
    int T; cin >> T;
    while (T --) solve();
    return 0;
}

题解：P9648 [SNCPC2019] Unrooted Trie

文章操作

简化题意

思路

上代码

相关推荐

评论

题解：P9648 [SNCPC2019] Unrooted Trie