牛客练习赛51 F ABCBA 树上路径+主席树

😊 | Powered By HeartFireY

Problem Analysis

题意分析：给出一个 n n n​个节点， n − 1 n - 1 n−1​​条边，再给出一条长度为 n n n​的字符串，字符串的每个字符对应树上编号 1 − n 1-n 1−n​​的节点，根据后面给出的边信息建立一颗类似字典树的结构。然后给出 q q q个询问，每个询问需要回答给定两个节点间路径上包含字串 A B C B A ABCBA ABCBA的数量。

我们首先分析如何求出树上路径：对于每个区间 [ l , r ] [l, r] [l,r]​，如果区间端点 l ,   r l,\ r l, r​不位于同一条链上，那么我们需要先求出他们的最近公共祖先 l c a ( l , r ) lca(l, r) lca(l,r)，然后将路径拆分为 [ l , x ] [l,x] [l,x]和 [ x , r ] [x, r] [x,r]​两条链进行计算。如下图所示：

例如从点 15 15 15到点 10 10 10之间的路径，我们可以分为 10 → 1 10\rightarrow1 10→1和 1 → 15 1\rightarrow15 1→15两段路径进行计算。

那么显然，对于任意区间端点不同链的情况，如果我们具有根节点到两个端点的两条链的信息，那么我们就可以求出全部的答案。也就是说，我们需要维护根节点到每个节点之间链的信息。那么我们可以对于每个节点建立一棵主席树，维护根节点到该节点间 A B C B A ABCBA ABCBA所有子串的信息。

信息怎么维护？这里显然不是简单的加和。对于任意单个节点而言，其只具有一个字母，只可能为 A 、 B 、 C A、B、C A、B、C或其他字母，为 A 、 B 、 C A、B、C A、B、C​之中的一个时，可以对答案(字串数目)产生一个贡献。但是当与其他节点进行组合时，可能会产生更多的贡献，比如 B B B​可以对 B C 、 B C B 、 B C B A BC、BCB、BCBA BC、BCB、BCBA​这几个串产生贡献。因此我们需要在维护区间和的时候用乘法原理将可能产生的贡献全部计算一次。

关于树上路径的部分，只需要一个树剖 L C A LCA LCA计算即可，如果位于同一条链上只需要查询一次即可，如果不位于同一条链上则需要按照上述的拆链组合方式进行查询，再组合计算。

真的没想到，，，字串的信息还可以这么维护…一开始打算套DP，想了半天没想出来咋搞。。。太菜了

Accepted Code

#include 
#define ll long long
using namespace std;

const int N = 3e4 + 10, MOD = 10007;

int n, q;
string str;
vector g[N];

int f[N][20], dep[N], root[N], cnt;
int lc[N  1;
    if(R  mid) return query(rc[rt], mid + 1, r, L, R);
    else return query(lc[rt], l, mid, L, R) + query(rc[rt], mid + 1, r, L, R);
}

void dfs(int u, int fa){
    f[u][0] = fa, dep[u] = dep[fa] + 1;
    for(int i = 1; i = dep[v]) u = f[u][i];
    if(u == v) return u;
    for(int i = 19; i >= 0; i--)
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline void solve(){
    int u, v; cin >> u >> v;
    int lcaa = lca(u, v), ans = 0;
    if(u == lcaa || v == lcaa){
        node tmp;
        if(u != lcaa) tmp = query(root[u], 1, n, dep[lcaa], dep[u]);
        else tmp = query(root[v], 1, n, dep[lcaa], dep[v]);
        ans += tmp.cat;
        ans %= MOD;
    }
    else{
        node t1 = query(root[u], 1, n, dep[lcaa], dep[u]);
        node t2 = query(root[v], 1, n, dep[lcaa] + 1, dep[v]);
        ans = (t1.cat + t2.cat + t1.A * t2.BCBA + t1.BA * t2.CBA + t1.CBA * t2.BA + t1.BCBA * t2.A) % MOD;
    }
    cout  q >> str;
    str = ' ' + str;
    for(int i = 1, u, v; i > u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 0; i