解题思路

给定一棵以 1 为根的树，每个点携带一个大写字母。对每次询问 $(u,v)$，取树上从 $u$ 到 $v$ 的简单路径，依次读出字母，判断这个序列是否包含子序列 "BUG"；若不包含则输出 YES，否则输出 NO。

核心建模：4 态自动机 + 函数复合

判断序列是否包含 "BUG" 可用一个 4 态自动机线性扫描完成：

• 状态 0：尚未读到 B
• 状态 1：已读到 B，未读到后续 U
• 状态 2：已读到 BU，未读到后续 G
• 状态 3：已读到 BUG（吸收态）

对单字符 ch 的转移：

• 在 0 且 ch=='B' → 1
• 在 1 且 ch=='U' → 2
• 在 2 且 ch=='G' → 3
• 其余转移不变

把“一段序列”的效果抽象为一个长度为 4 的函数数组 f[0..3]：f[s] 表示从状态 s 出发，扫描该段后落到的终止状态。两段序列拼接的总体效果就是函数复合：若先扫段 A 再扫段 B，则整体函数 F = F_B ∘ F_A。便于实现，我们定义拼接运算：

op_concat(A, B) = B ∘ A    # 先 A 再 B

树上路径方向与数据结构

路径 $u \to v$ 可以拆为两部分：

• $u \to \mathrm{LCA}(u,v)$ 的自底向上部分（不含 LCA）
• $\mathrm{LCA}(u,v) \to v$ 的自顶向下部分（含 LCA）

用重链剖分（HLD）+ 线段树加速链内区间查询。对每条重链按“链顶→链底”的顺序线性化；在线段树每个结点上同时维护两种方向的区间函数：

• F_lr：区间按自顶向下扫描（left→right）得到的函数；
• F_rl：区间按自底向上扫描（right→left）得到的函数。

单点（叶子）两者相同，都是该字母的“单字符函数”。 区间合并（设左儿子 A 覆盖 [L,mid]，右儿子 B 覆盖 [mid+1,R]）：

• F_lr([L,R]) = F_lr(B) ∘ F_lr(A)（先扫 A 再扫 B）
• F_rl([L,R]) = F_rl(A) ∘ F_rl(B)（反向等价于先扫右儿子 B（靠下）再扫左儿子 A（靠上），实现时写成 left ∘ right）

关键细节（本题易错点，两处修正）

1. 反向区间查询的合并方向 做线段树查询 F_rl 时，命中左端点的段应拼到右侧，命中右端点的段应拼到左侧，保证整体是“自底向上”的真实顺序。

2. 下半段（LCA→v）链段的拼接顺序 重链剖分从 v 不断跳到上方时，遇到的链段顺序与真实路径顺序相反。因此在累积 downF 时必须把新得到的链段函数“前置”拼接： 把

downF = op_concat(downF, seg)    # 错：把 seg 放在后面，顺序被反转

改为

downF = op_concat(seg, downF)    # 对：把 seg 放在前面，顺序正确

最终总函数 F_total = F_down ∘ F_up（先上半段，再下半段）。把初始状态 0 代入，若得到 3 表示出现 "BUG"，输出 NO，否则 YES。

复杂度分析

• 预处理（两次 DFS + 建线段树）：$O(n)$
• 单次询问：重链剖分分解为 $O(\log n)$ 个链段，每段区间查询与 4 态函数复合均为 $O(1)$，故 $O(\log n)$
• 总计：$O\big((n+q)\log n\big)$ 时间，$O(n)$ 空间

代码实现

Python

# -*- coding: utf-8 -*-
# 解法：HLD + 线段树，维护区间正向/反向的4态自动机函数。
import sys
sys.setrecursionlimit(1 << 25)

# ---- 自动机：单字符函数 / 复合 / 恒等 ----
def letter_func(ch):
    f = [0, 1, 2, 3]
    if ch == 'B':
        f[0] = 1
    elif ch == 'U':
        f[1] = 2
    elif ch == 'G':
        f[2] = 3
    return f

def compose(g, f):
    # g ∘ f：先 f 后 g
    return [g[f[i]] for i in range(4)]

IDF = [0, 1, 2, 3]

def op_concat(a, b):
    # 先 a 再 b
    return compose(b, a)

# ---- 读入 ----
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it)); q = int(next(it))

father = [0]*(n+1)
for i in range(1, n+1):
    father[i] = int(next(it))

# 字母可能是一整串，也可能被拆成多个 token，这里拼到 n 个即可
letters = ['']
s = next(it)
while len(s) < n:
    s += next(it)
letters.append(s)  # 索引 1 的位置放整串
# 方便按节点 i 取字母：letters_str[i]
letters_str = ' ' + s

queries = []
for _ in range(q):
    u = int(next(it)); v = int(next(it))
    queries.append((u, v))

# ---- 建树（无向边）----
g = [[] for _ in range(n+1)]
for i in range(2, n+1):
    p = father[i]
    if p != 0:
        g[p].append(i)
        g[i].append(p)

# ---- HLD 预处理 ----
size = [0]*(n+1)
dep  = [0]*(n+1)
par  = [0]*(n+1)
heavy= [-1]*(n+1)

def dfs1(u, p):
    par[u] = p
    dep[u] = dep[p] + 1 if p != 0 else 0
    size[u] = 1
    mx = 0
    for v in g[u]:
        if v == p: continue
        dfs1(v, u)
        size[u] += size[v]
        if size[v] > mx:
            mx = size[v]
            heavy[u] = v

dfs1(1, 0)

head = [0]*(n+1)
pos  = [0]*(n+1)
rpos = [0]*(n+1)
cur = 0

def dfs2(u, h):
    global cur
    head[u] = h
    cur += 1
    pos[u] = cur
    rpos[cur] = u
    if heavy[u] != -1:
        dfs2(heavy[u], h)
        for v in g[u]:
            if v != par[u] and v != heavy[u]:
                dfs2(v, v)

dfs2(1, 1)

# ---- 线段树：存正向 FLR 与反向 FRL ----
size_pow2 = 1
while size_pow2 < n: size_pow2 <<= 1

FLR = [[0,1,2,3] for _ in range(2*size_pow2)]  # top->bottom
FRL = [[0,1,2,3] for _ in range(2*size_pow2)]  # bottom->top

# 叶子
for i in range(1, n+1):
    node = rpos[i]
    f = letter_func(letters_str[node])
    FLR[size_pow2 + i - 1] = f[:]
    FRL[size_pow2 + i - 1] = f[:]
# 空位置恒等
for i in range(size_pow2 + n, 2*size_pow2):
    FLR[i] = IDF[:]; FRL[i] = IDF[:]

# 向上建树
for i in range(size_pow2 - 1, 0, -1):
    # 正向：right ∘ left（先左后右）
    FLR[i] = op_concat(FLR[2*i], FLR[2*i+1])
    # 反向：left ∘ right（等价先扫靠下的右，再靠上的左）
    FRL[i] = op_concat(FRL[2*i+1], FRL[2*i])

def query_lr(l, r):
    """查询 [l,r] 的自顶向下函数"""
    if l > r: return IDF[:]
    l += size_pow2 - 1; r += size_pow2 - 1
    resL = IDF[:]; resR = IDF[:]
    while l <= r:
        if (l & 1) == 1:
            resL = op_concat(resL, FLR[l]); l += 1
        if (r & 1) == 0:
            resR = op_concat(FLR[r], resR); r -= 1
        l >>= 1; r >>= 1
    return op_concat(resL, resR)

def query_rl(l, r):
    """查询 [l,r] 的自底向上函数（合并方向需对调）"""
    if l > r: return IDF[:]
    l += size_pow2 - 1; r += size_pow2 - 1
    resL = IDF[:]; resR = IDF[:]
    while l <= r:
        if (l & 1) == 1:
            # 左端命中段放到右侧
            resR = op_concat(FRL[l], resR); l += 1
        if (r & 1) == 0:
            # 右端命中段放到左侧
            resL = op_concat(resL, FRL[r]); r -= 1
        l >>= 1; r >>= 1
    return op_concat(resL, resR)

def lca(u, v):
    while head[u] != head[v]:
        if dep[head[u]] > dep[head[v]]:
            u = par[head[u]]
        else:
            v = par[head[v]]
    return u if dep[u] < dep[v] else v

def path_good(u, v):
    w = lca(u, v)

    # 上半段：u -> w（不含 w），反向查询，顺序“追加在后”
    upF = IDF[:]
    x = u
    while head[x] != head[w]:
        upF = op_concat(upF, query_rl(pos[head[x]], pos[x]))
        x = par[head[x]]
    if pos[w] + 1 <= pos[x]:
        upF = op_concat(upF, query_rl(pos[w] + 1, pos[x]))

    # 下半段：w -> v（含 w），正向查询，注意“前置拼接”（关键修正）
    downF = IDF[:]
    y = v
    while head[y] != head[w]:
        downF = op_concat(query_lr(pos[head[y]], pos[y]), downF)  # 前置
        y = par[head[y]]
    downF = op_concat(query_lr(pos[w], pos[y]), downF)            # 前置

    totalF = compose(downF, upF)  # 先上段再下段
    return totalF[0] != 3

# ---- 回答询问 ----
out = []
for u, v in queries:
    out.append("YES" if path_good(u, v) else "NO")
print("\n".join(out))

Java

// 解法：HLD + 线段树维护区间的正/反两种扫描函数（4态自动机）。
// 修正点：1) 反向区间查询 queryRL 的合并方向；2) 下半段(LCA->v)的链段“前置拼接”。
import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int p = 0, n = 0;
        FastScanner(InputStream is){ in = is; }
        private int read() throws IOException {
            if (p >= n) { n = in.read(buf); p = 0; if (n <= 0) return -1; }
            return buf[p++];
        }
        int nextInt() throws IOException {
            int c, s = 1, x = 0;
            do { c = read(); } while (c <= ' ' && c != -1);
            if (c == '-') { s = -1; c = read(); }
            while (c > ' ') { x = x*10 + (c-'0'); c = read(); }
            return x * s;
        }
        String next() throws IOException {
            int c; StringBuilder sb = new StringBuilder();
            do { c = read(); } while (c <= ' ' && c != -1);
            while (c > ' ') { sb.append((char)c); c = read(); }
            return sb.toString();
        }
    }

    static int n, q;
    static ArrayList<Integer>[] g;
    static int[] size, dep, par, heavy, head, pos, rpos;
    static int curPos;

    static int sizePow2;
    static int[][] FLR, FRL;
    static final int[] IDF = new int[]{0,1,2,3};

    static int[] letterFunc(char ch){
        int[] f = new int[]{0,1,2,3};
        if (ch=='B') f[0] = 1;
        else if (ch=='U') f[1] = 2;
        else if (ch=='G') f[2] = 3;
        return f;
    }
    static int[] compose(int[] g, int[] f) {
        int[] r = new int[4];
        for (int i=0;i<4;i++) r[i] = g[f[i]];
        return r;
    }
    static int[] opConcat(int[] a, int[] b){
        // 先 a 再 b
        return compose(b, a);
    }

    static void dfs1(int u, int p){
        par[u]=p;
        dep[u]=(p==0?0:dep[p]+1);
        size[u]=1;
        int mx=0; heavy[u]=-1;
        for (int v: g[u]) if (v!=p){
            dfs1(v,u);
            size[u]+=size[v];
            if (size[v] > mx){ mx=size[v]; heavy[u]=v; }
        }
    }
    static void dfs2(int u, int h){
        head[u]=h; pos[u]=++curPos; rpos[curPos]=u;
        if (heavy[u]!=-1){
            dfs2(heavy[u], h);
            for (int v: g[u]){
                if (v!=par[u] && v!=heavy[u]) dfs2(v, v);
            }
        }
    }

    static int[] queryLR(int l, int r){
        if (l>r) return IDF.clone();
        int L = l + sizePow2 - 1, R = r + sizePow2 - 1;
        int[] resL = IDF.clone(), resR = IDF.clone();
        while (L<=R){
            if ((L & 1)==1){ resL = opConcat(resL, FLR[L]); L++; }
            if ((R & 1)==0){ resR = opConcat(FLR[R], resR); R--; }
            L >>= 1; R >>= 1;
        }
        return opConcat(resL, resR);
    }
    static int[] queryRL(int l, int r){
        if (l>r) return IDF.clone();
        int L = l + sizePow2 - 1, R = r + sizePow2 - 1;
        int[] resL = IDF.clone(), resR = IDF.clone();
        while (L<=R){
            if ((L & 1)==1){ // 左端命中段放右侧（关键修正）
                resR = opConcat(FRL[L], resR); L++;
            }
            if ((R & 1)==0){ // 右端命中段放左侧
                resL = opConcat(resL, FRL[R]); R--;
            }
            L >>= 1; R >>= 1;
        }
        return opConcat(resL, resR);
    }

    static int lca(int u, int v){
        while (head[u]!=head[v]){
            if (dep[head[u]]>dep[head[v]]) u = par[head[u]];
            else v = par[head[v]];
        }
        return dep[u]<dep[v]?u:v;
    }

    static boolean pathGood(int u, int v){
        int w = lca(u, v);

        // 上半段：u -> w（不含 w），反向，顺序“追加在后”
        int[] upF = IDF.clone();
        int x = u;
        while (head[x]!=head[w]){
            upF = opConcat(upF, queryRL(pos[head[x]], pos[x]));
            x = par[head[x]];
        }
        if (pos[w]+1 <= pos[x]){
            upF = opConcat(upF, queryRL(pos[w]+1, pos[x]));
        }

        // 下半段：w -> v（含 w），正向，注意“前置拼接”（关键修正）
        int[] downF = IDF.clone();
        int y = v;
        while (head[y]!=head[w]){
            downF = opConcat(queryLR(pos[head[y]], pos[y]), downF); // 前置
            y = par[head[y]];
        }
        downF = opConcat(queryLR(pos[w], pos[y]), downF);           // 前置

        int[] totalF = compose(downF, upF); // 先上段再下段
        return totalF[0] != 3;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        n = fs.nextInt(); q = fs.nextInt();

        int[] father = new int[n+1];
        for (int i=1;i<=n;i++) father[i] = fs.nextInt();

        String s = fs.next();
        while (s.length() < n) s += fs.next();
        char[] letters = new char[n+1];
        for (int i=1;i<=n;i++) letters[i] = s.charAt(i-1);

        g = new ArrayList[n+1];
        for (int i=0;i<=n;i++) g[i] = new ArrayList<>();
        for (int i=2;i<=n;i++){
            int p = father[i];
            if (p!=0){ g[p].add(i); g[i].add(p); }
        }

        size = new int[n+1];
        dep  = new int[n+1];
        par  = new int[n+1];
        heavy= new int[n+1];
        head = new int[n+1];
        pos  = new int[n+1];
        rpos = new int[n+1];

        dfs1(1,0);
        curPos = 0;
        dfs2(1,1);

        sizePow2 = 1; while (sizePow2 < n) sizePow2 <<= 1;
        FLR = new int[2*sizePow2][4];
        FRL = new int[2*sizePow2][4];
        for (int i=0;i<2*sizePow2;i++){
            for (int j=0;j<4;j++){ FLR[i][j]=IDF[j]; FRL[i][j]=IDF[j]; }
        }
        // 叶子
        for (int i=1;i<=n;i++){
            int node = rpos[i];
            int[] f = letterFunc(letters[node]);
            FLR[sizePow2 + i - 1] = f.clone();
            FRL[sizePow2 + i - 1] = f.clone();
        }
        // 向上建树
        for (int i=sizePow2-1;i>=1;i--){
            // 正向：right ∘ left
            FLR[i] = opConcat(FLR[2*i], FLR[2*i+1]);
            // 反向：left ∘ right
            FRL[i] = opConcat(FRL[2*i+1], FRL[2*i]);
        }

        StringBuilder out = new StringBuilder();
        for (int i=0;i<q;i++){
            int u = fs.nextInt(), v = fs.nextInt();
            out.append(pathGood(u, v) ? "YES" : "NO").append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

// 解法：重链剖分 + 线段树，区间维护正/反两种方向的4态自动机函数。
// 修正点：1) 反向 query_rl 合并方向；2) 下半段 (LCA->v) “前置拼接”。
#include <bits/stdc++.h>
using namespace std;

struct Func {
    int f[4];
    Func(){ f[0]=0; f[1]=1; f[2]=2; f[3]=3; } // 恒等
    static Func letter(char ch){
        Func r;
        if (ch=='B') r.f[0]=1;
        else if (ch=='U') r.f[1]=2;
        else if (ch=='G') r.f[2]=3;
        return r;
    }
};
inline Func compose(const Func& g, const Func& f){
    Func r;
    for (int i=0;i<4;i++) r.f[i] = g.f[f.f[i]];
    return r;
}
inline Func op_concat(const Func& a, const Func& b){
    // 先 a 再 b
    return compose(b, a);
}

int n, q;
vector<vector<int>> g;
vector<int> sz, dep, par, heavy, head_, pos, rpos;
int curPos;

int SZ;
vector<Func> FLR, FRL;

void dfs1(int u, int p){
    par[u]=p;
    dep[u]=(p==0?0:dep[p]+1);
    sz[u]=1;
    int mx=0; heavy[u]=-1;
    for (int v: g[u]) if (v!=p){
        dfs1(v,u);
        sz[u]+=sz[v];
        if (sz[v]>mx){ mx=sz[v]; heavy[u]=v; }
    }
}
void dfs2(int u, int h){
    head_[u]=h;
    pos[u]=++curPos;
    rpos[curPos]=u;
    if (heavy[u]!=-1){
        dfs2(heavy[u], h);
        for (int v: g[u]){
            if (v!=par[u] && v!=heavy[u]) dfs2(v, v);
        }
    }
}

Func query_lr(int l, int r){
    if (l>r) return Func();
    int L = l + SZ - 1, R = r + SZ - 1;
    Func resL, resR;
    while (L<=R){
        if (L & 1){ resL = op_concat(resL, FLR[L]); L++; }
        if (!(R & 1)){ resR = op_concat(FLR[R], resR); R--; }
        L >>= 1; R >>= 1;
    }
    return op_concat(resL, resR);
}
Func query_rl(int l, int r){
    if (l>r) return Func();
    int L = l + SZ - 1, R = r + SZ - 1;
    Func resL, resR;
    while (L<=R){
        if (L & 1){                 // 左端命中段放右侧（关键修正）
            resR = op_concat(FRL[L], resR); L++;
        }
        if (!(R & 1)){              // 右端命中段放左侧
            resL = op_concat(resL, FRL[R]); R--;
        }
        L >>= 1; R >>= 1;
    }
    return op_concat(resL, resR);
}

int lca(int u, int v){
    while (head_[u]!=head_[v]){
        if (dep[head_[u]]>dep[head_[v]]) u = par[head_[u]];
        else v = par[head_[v]];
    }
    return dep[u]<dep[v]?u:v;
}

bool path_good(int u, int v){
    int w = lca(u, v);

    // 上半段：u -> w（不含 w），反向，顺序“追加在后”
    Func upF;
    int x=u;
    while (head_[x]!=head_[w]){
        upF = op_concat(upF, query_rl(pos[head_[x]], pos[x]));
        x = par[head_[x]];
    }
    if (pos[w]+1 <= pos[x]){
        upF = op_concat(upF, query_rl(pos[w]+1, pos[x]));
    }

    // 下半段：w -> v（含 w），正向，注意“前置拼接”（关键修正）
    Func downF;
    int y=v;
    while (head_[y]!=head_[w]){
        downF = op_concat(query_lr(pos[head_[y]], pos[y]), downF); // 前置
        y = par[head_[y]];
    }
    downF = op_concat(query_lr(pos[w], pos[y]), downF);            // 前置

    Func totalF = compose(downF, upF); // 先上段再下段
    return totalF.f[0] != 3;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    vector<int> father(n+1);
    for (int i=1;i<=n;i++) cin >> father[i];

    string s, t; 
    cin >> s; 
    while ((int)s.size() < n){ cin >> t; s += t; }
    vector<char> letter(n+1);
    for (int i=1;i<=n;i++) letter[i] = s[i-1];

    g.assign(n+1, {});
    for (int i=2;i<=n;i++){
        int p = father[i];
        if (p!=0){ g[p].push_back(i); g[i].push_back(p); }
    }

    sz.assign(n+1,0);
    dep.assign(n+1,0);
    par.assign(n+1,0);
    heavy.assign(n+1,-1);
    head_.assign(n+1,0);
    pos.assign(n+1,0);
    rpos.assign(n+1,0);

    dfs1(1,0);
    curPos = 0;
    dfs2(1,1);

    SZ = 1; while (SZ < n) SZ <<= 1;
    FLR.assign(2*SZ, Func());
    FRL.assign(2*SZ, Func());
    for (int i=1;i<=n;i++){
        int node = rpos[i];
        Func f = Func::letter(letter[node]);
        FLR[SZ + i - 1] = f;
        FRL[SZ + i - 1] = f;
    }
    for (int i=SZ-1;i>=1;i--){
        // 正向：right ∘ left
        FLR[i] = op_concat(FLR[2*i], FLR[2*i+1]);
        // 反向：left ∘ right
        FRL[i] = op_concat(FRL[2*i+1], FRL[2*i]);
    }

    while (q--){
        int u, v; cin >> u >> v;
        cout << (path_good(u, v) ? "YES" : "NO") << '\n';
    }
    return 0;
}

题目内容

小美有一个结点总数为 $n$ 且根节点编号为 $1$ 的有根树。

第 $i$ 个结点的编号为 $i$ ,所携带的字母为 $a_i$。

小美是一名程序员,她认为一对 $(u,v)$ 是好对,当且仅当从节点 $u$ 到节点 $v$ 的简单路径上依次拼接得到字符串 $S$ 的子序列中不存在"$BUG$"。

小美会提出 $q$ 次询问,你需要帮助她回答$(u,v)$是不是好对。

子序列:子序列是原始序列的一个子集，其元素顺序保持不变，但可以选择性地删除一些元素。换句话说，子序列是从原始序列中挑选出来的元素集合，这些元素在原始序列中的相对顺序保持一致。

例如:$S=BAUCDEG$,"$BUG$"为字符串 $S$ 的一个子序列,但"$BGA$"不是 $S$ 的子序列。

输入描述

第一行两个整数 $n,q(3 ≤ n,q ≤ 10^5)$,分别表示节点个数和询问次数。

第二行 $n$ 个整数,第 $i$ 个为 $father_i(1 ≤ father_i ≤ i-1)$,表示第 $i$ 个节点的父节点,特别的 $father_1= 0$ 。

第三行 $n$ 个字母,第 $i$ 个为 $a_i('A'≤ a_i<'Z')$,表示第 $i$ 个节点所携带的字母。

接下来 $q$ 行,每行两个墪数 $u,v(1 ≤ u ≠ ≤ n)$,表示询问的起点和终点。

输出描述

共 $q$ 行,每行一个字符串,若 $(u,v)$ 是好对输出"$YES$",否则输出"$NO$"。

样例1

输入

5 3
0 1 1 2 2
AUGBC
4 3
4 5
4 1

输出

NO
YES
YES