题解：P9648 [SNCPC2019] Unrooted Trie

· · 题解

简化题意

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

1\le \sum n\le 10^6

思路

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

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

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

我们先暂定1 为根。为了方便，以下称“当下”指在以 1 为根的树中。

当我们在遍历树的时候，如果遇到一个点 u 连出的边中有相同时：

  1. 相同的边不少于 3 条：这无论如何怎么选根，这个点必定有两个连向儿子的相同的边。直接退出输出 0。

  2. 那么接下来只有一对边相同。当下两边均连向儿子：我们只能选择两儿子的子树中的点为根，不然两儿子必定仍然是这个节点的儿子。

  3. 当下一条边连向父亲，一条边连向儿子 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)。

上代码

#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;
}