P6088 [JSOI2015] 字符串树

2025-05-22

感谢 @GUAIKATTO 给我推题目，❤️❤️❤️。

作战记录:

tag: 树剖 Trie

写了一小时但 0 行有用的代码。。。然后果断看题解，然后重写就过了。

题意

给一棵树，每条边都是无向边且边权为一个字符串，需要回答 Q 次询问，每次问 \(u\) 到 \(v\) 的简单路径上，字符串 \(s\) 是多少条边的前缀。

\(|s| \le 10\)， \(n, q \le 10 ^ 5\)。

思路

没想到啊，虽然我是想到了树上的路径肯定得转换成 LCA 来求的，但是我后来去想的是每个节点开一个 trie。。。这样肯定是不太行呀，空间要很大而且很难写的。

麻了，其实太久没用过 trie 了，本来 Insert 啥的都忘了，然后对这个要的空间也不太清楚。

不过其实是不是思路离 ac 只差一点了！都想到树剖了，咋没想到就是可以把询问都拆成 \([l, r, s]\) 这种格式。

好吧其实也想到了，但是这玩意看起来就很难处理呀。trie 可以 insert，但也没见过删除的吧。。。幸好不能删除，其实你能删除的话，这个也搞不了呀。这个不就是一个很经典的扫描线呀😅，把 \([1, l - 1]\) 的答案减去，再把 \([1, r]\) 的答案加回来，不就写出来了吗？

代码

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

constexpr int N = int(1e5) + 5;
int siz[N], dep[N], fa[N], son[N], dfn[N], top[N], seg[N];

struct edge {
    int u, v;
    string s;
};
struct ques{
    int l, r, idx;
    string s;
};
int trie[N * 10][26], cnt[N * 10];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    vector<string> t(n + 1);
    vector<edge> Edge(n);
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        string s;
        cin >> u >> v >> s;
        Edge[i] = {u, v, s};
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto dfs1 = [&](auto &&self, int u, int pre) -> void {
        fa[u] = pre, siz[u] = 1, dep[u] = dep[pre] + 1;
        for (auto v : g[u]) {
            if (v == pre) continue;
            self(self, v, u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]])
                son[u] = v;
        }
    };
    dfs1(dfs1, 1, 0);
    {
        int tot = 0;
        auto dfs2 = [&](auto &&self, int u, int pre) -> void{
            dfn[u] = ++tot, seg[tot] = u;
            if(son[pre] == u) top[u] = top[pre];
            else top[u] = u;
            if(son[u]) self(self, son[u], u);
            for(auto v : g[u]){
                if(v == pre || v == son[u]) continue;
                self(self, v, u);
            }
        };
        dfs2(dfs2, 1, 0);
    }
    for(int i = 1; i < n; i++){
        auto [u, v, s] = Edge[i];
        if(dep[u] > dep[v]) swap(u, v);
        t[v] = s;
    }
    int q;
    cin >> q;
    vector<ques> Q;
    for(int k = 0; k < q; k++){
        int u, v;
        string s;
        cin >> u >> v >> s;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            Q.push_back({dfn[top[u]], dfn[u], k, s});
            u = fa[top[u]];
        }
        if(u != v){
            if(dep[u] > dep[v]) swap(u, v);
            Q.push_back({dfn[u] + 1, dfn[v], k, s});
        }
    }
    ranges::sort(Q, [](ques x, ques y){
        return x.l < y.l;
    });
    auto cmp = [](ques x, ques y){
        return x.r > y.r;
    };
    priority_queue<ques, vector<ques>, decltype(cmp)> pq(cmp);
    vector<int> ans(q);
    auto query = [&](string s){
        int cur = 0;
        for(auto x : s){
            if(trie[cur][x - 'a'] == 0) return 0;
            cur = trie[cur][x - 'a'];
        }
        return cnt[cur];
    };
    int tot = 0;
    auto Insert = [&](string s){
        int cur = 0;
        for(auto x : s){
            if(trie[cur][x - 'a'] == 0){
                trie[cur][x - 'a'] = ++tot;
            }
            cur = trie[cur][x - 'a'];
            cnt[cur]++;
        }
    };
    for(int i = 2, j = 0; i <= n; i++){
        while(j < Q.size() && Q[j].l == i){
            // cerr << j << " \n";
            ans[Q[j].idx] -= query(Q[j].s);
            pq.push(Q[j++]);
        }
        Insert(t[seg[i]]);
        while(!pq.empty() && pq.top().r == i){
            auto [l, r, idx, s] = pq.top();
            // cerr << l << "  " << r << '\n';
            pq.pop();
            ans[idx] += query(s);
        }
    }
    // cerr << "query: " << query("ab") << '\n';
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

总结

多写就好。。。

注意要会稍微算一下 trie 的空间，像这题，必须差不多开 \(10n\) 的空间，因为你一个字符串，最多可能会增加 \(10\) 个点，其实挺好分析的。

然后像计数以及状态啥的，都是只用看 \(trie_{cur,c}\) 这种，像这题的 \(cnt\) 数组，这个是之前一个 CF 题 CF2093G 用过 trie，其他时候还真没用过。

然后没有啥想说的了吧，但就是感觉这题像这样，印象不会很深刻，如果是自己能想出来，肯定收获更多，记下来偶尔翻翻会好点。还好自己思考了下吧，直接看题解肯定更不爽。