2026-06-13：查询树上回文路径。用go语言，给定一棵包含 n 个节点的无向树（节点编号为 0 到 n-1），树用数组 edges 表示：edge…

2026-06-13：查询树上回文路径。用go语言，给定一棵包含 n 个节点的无向树（节点编号为 0 到 n-1），树用数组 edges 表示：edges 的长度为 n-1，每个元素为 [u, v]，表示节点 u 与 v 之间有一条无向边。

另外给定一个字符串 s（长度为 n，只包含小写英文字母），其中 s[i] 是分配给节点 i 的字符。

再给定若干操作 queries，每条操作有两种格式之一：

• update u c：把节点 u 的字符更新为 c，即令 s[u] = c。

• query u v：考虑从节点 u 到节点 v 的唯一路径（包含 u 和 v 这两个端点）。把这条路径上

• 所有节点对应的字符依次取出，组成一个字符串。判断这个字符串的字符能否通过重排得到一个回文串（回文串指正着读和反着读相同）。

需要为每条 query 结果返回一个布尔值：能重排成回文串则为 true，否则为 false。返回结果按 queries 中出现的 query 顺序组成数组。

1 <= n == s.length <= 5 * 10000。

edges.length == n – 1。

edges[i] = [ui, vi]。

0 <= ui, vi <= n – 1。

s 由小写英文字母组成。

输入生成的 edges 表示一棵有效的树。

1 <= queries.length <= 5 * 10000。

queries[i] = “update ui c” 或

queries[i] = “query ui vi”。

0 <= ui, vi <= n – 1。

c 是一个小写英文字母。

输入： n = 3, edges = [[0,1],[1,2]], s = “aac”, queries = [“query 0 2″,”update 1 b”,”query 0 2″]。

输出： [true,false]。

解释：

“query 0 2″：路径 0 → 1 → 2 得到的字符串是 “aac”，可以重新排列形成 “aca”，这是一个回文串。因此，answer[0] = true。

“update 1 b”：将节点 1 更新为 ‘b’，现在 s = “abc”。

“query 0 2″：路径上的字符为 “abc”，无法重新排列形成回文串。因此，answer[1] = false。

因此，answer = [true, false]。

题目来自力扣3841。

一、整体解题核心原理（前置铺垫） 1. 字符串可重排成回文的判定规则

一个字符串打乱后能构成回文，充要条件：最多只有1种字符出现奇数次，其余全部偶数次。
用二进制掩码简化统计：26个小写字母对应26位二进制数，第k位为1代表字母'a'+k出现次数为奇数，0代表偶数；异或运算恰好能实现“次数奇偶翻转”。

• 路径字符总奇偶掩码：二进制中1的数量 ≤ 1 → 输出true，否则false；

• 判断掩码1的个数：mask & (mask-1) == 0，仅0个/1个1时等式成立。

2. 树上两点路径异或掩码数学公式

树上u到v的路径 = 根→u + 根→v – 2×根→LCA(u,v) + LCA本身
异或性质：同一个数异或两次会抵消（x^x=0），因此路径原始静态掩码公式：
xor(u,v) = rootXor[u] ^ rootXor[v] ^ rootXor[lca] ^ rootXor[lca] ^ val(lca)
化简：xor(u,v) = rootXor[u] ^ rootXor[v] ^ val(lca)

3. 单点字符修改的难点与树状数组差分方案

普通静态前缀掩码只能处理不变字符，本题有update单点修改：修改节点x字符，等价于x整棵子树内所有点的根前缀掩码全部异或一个修正值val。
原因：任意节点y在x子树内，根到y的路径一定会经过x；x字符改变，所有子树节点的根路径奇偶掩码全部翻转。
DFS时间戳将子树映射为连续区间[in[x], out[x]]，区间异或更新用差分树状数组（异或版Fenwick）实现：

• 区间[l, r]异或val：update(l, val)、update(r+1, val)；

• 查询单点in[x]的全局修正总掩码：树状数组前缀异或pre(in[x])；

• 最终真实根前缀掩码 = 原始静态rootXor[x] ^ 全局修正掩码pre(in[x])。

4. LCA求解方式：二进制倍增

预处理每个节点2^k级祖先，O(logn)求两点最近公共祖先，适配5e4规模数据。

二、代码完整分步执行流程（不含代码，纯逻辑拆解） 阶段1：输入数据初始化与无向树建邻接表

1. 读取节点总数n、边数组edges、初始字符串s、操作数组queries；

2. 构建大小为n的邻接表g：遍历每条边[u,v]，双向添加（无向树），g[u]追加v、g[v]追加u；

3. 预分配全局存储数组：

• dep[]：每个节点深度；

• timeIn[]/timeOut[]：DFS入、出时间戳，标记子树区间；

• pa[][]：倍增祖先表，pa[x][k]代表节点x向上跳2^k步的祖先；

• pathXorFromRoot[]：静态根前缀异或掩码，未修改字符时的原始奇偶掩码；

• t[]：字节数组，实时保存每个节点当前字符，响应update修改；

• clock：时间戳计数器，初始0。

阶段2：DFS遍历，完成时间戳、深度、静态掩码、一级祖先预处理

根固定为节点0，递归DFS(x, 父节点p)：

1. 记录x的2^0级祖先pa[x][0] = p；

2. 时间戳clock自增，赋值timeIn[x] = clock；

3. 计算静态根掩码pathXorFromRoot[x]：父节点静态掩码 异或 当前节点字符对应二进制位；根节点0单独初始化掩码为自身字符；

4. 遍历x所有邻接子节点y，跳过父节点p：

• 子节点深度dep[y] = dep[x]+1；

• 递归执行DFS(y, x)；

5. 所有子节点遍历完成后，赋值timeOut[x] = clock；此时x的整棵子树对应时间戳连续区间[timeIn[x], timeOut[x]]。

阶段3：预处理二进制倍增祖先表（完整2^k级祖先）

1. 计算最大倍增层数mx：取n二进制位数，保证2^mx覆盖树最大深度；

2. 逐层递推填充pa数组：从k=0到mx-2，遍历所有节点x：

• 若x的2^k级祖先p≠-1，则x的2^(k+1)级祖先 = p的2^k级祖先；

• 若p=-1（无上层祖先），则pa[x][k+1] = -1；
完成后可通过倍增快速向上跳任意步数。

阶段4：封装两个工具函数 工具1：uptoDep(x, d)

将节点x向上跳，直到深度等于d：

1. 计算需要向上跳的步数差值k = dep[x]-d；

2. 循环取出k最低位2^t，x跳至pa[x][t]，清除最低位，直到k=0；返回调整深度后的节点。

工具2：getLCA(x, y)，求两点最近公共祖先

1. 保证y深度更深，若dep[x]>dep[y]则交换x、y；

2. 调用uptoDep把y上跳到与x同一深度；

3. 若x==y，直接返回x为LCA；

4. 从最大倍增层向下遍历到0：若x、y当前2^k祖先不相同，同步将x、y跳至各自祖先；

5. 循环结束后x、y父节点即为LCA，返回pa[x][0]。

阶段5：初始化异或型树状数组Fenwick

1. 树状数组长度n+1（时间戳从1开始，下标1~n）；

2. 树状数组重载异或更新、前缀异或查询逻辑，替代普通加法；

3. 作用：维护所有update操作带来的区间异或修正，单点查询得到该节点累计修正掩码。

阶段6：逐行处理每一条查询操作，分两类分支 分支A：操作是 update u c（修改节点u字符为c）

1. 提取目标节点编号u、新字符c，读取节点u当前旧字符t[u]；

2. 计算修正掩码val：旧字符二进制位 异或 新字符二进制位；val代表u子树所有节点掩码需要翻转的数值；

3. 更新全局字符数组t[u] = c，保存最新字符；

4. 对子树区间[timeIn[u], timeOut[u]]执行区间异或更新：

• 树状数组更新 timeIn[u] 位置，异或val；

• 树状数组更新 timeOut[u]+1 位置，异或val；
差分原理：区间内前缀查询会叠加val，区间外抵消为0。

分支B：操作是 query x y（查询x到y路径能否重排回文）

1. 提取两个端点x、y；调用getLCA得到两点公共祖先lca；

2. 分别查询x、y时间戳对应的累计修正掩码：fx = f.pre(timeIn[x])，fy = f.pre(timeIn[y])；

3. 计算两点实时真实根前缀掩码：
realX = pathXorFromRoot[x] ^ fx
realY = pathXorFromRoot[y] ^ fy

4. 套路径掩码公式计算整条路径总奇偶掩码：
totalMask = realX ^ realY ^ (1 << (t[lca]-‘a’))
推导说明：realX^realY抵消根到LCA两段路径，缺少LCA自身字符，需单独补上；

5. 判断回文条件：totalMask二进制中1的数量≤1，等价于totalMask & (totalMask-1) == 0；

6. 将布尔结果存入答案数组ans。

阶段7：所有操作处理完毕，返回ans数组作为最终输出三、样例输入完整推演（辅助理解流程）

输入：n=3，边0-1、1-2，初始s=aac，查询3条

1. DFS后时间戳：in[0]=1,in[1]=2,in[2]=3；out[0]=3,out[1]=3,out[2]=3；
静态掩码：pathXor[0]=001(a)、pathXor[1]=001^010(a^a)=000、pathXor[2]=000^100(c)=100；

2. 第一条query 0 2：
LCA=1；无update修正fx=fy=0；
totalMask=001 ^ 100 ^ 010(lca字符a)=111；二进制两个1，满足≤1 → true；

3. update 1 b：旧字符a(001)，新b(010)，val=011；区间[2,3]异或011；

4. 第二条query 0 2：
fx=pre(1)=0，fy=pre(3)=011；
realX=001^0=001，realY=100^011=111；
totalMask=001^111 ^ 010(lca现在是b)=100；二进制3个1 → false；
输出 [true,false]，与样例匹配。

四、总时间复杂度分析

设节点数量n，查询操作数量q（n、q上限均5e4），倍增层数log₂n≈16。

1. 预处理阶段复杂度

1. 建邻接表：O(n)

2. DFS遍历整棵树：O(n)

3. 倍增祖先表填充：O(n·logn)
总预处理：O(n logn)

2. 每条操作复杂度

• update操作：两次树状数组更新，单次Fenwick O(logn) → O(logn)

• query操作：1次LCA（O(logn)）+ 两次Fenwick前缀查询（各O(logn)）+ 简单位运算 → O(logn)
全部q次操作总复杂度：O(q logn)

整体总时间复杂度

O((n + q) · logn)
n、q均5e4，logn≈16，总运算量可控，满足数据范围要求。

五、总额外空间复杂度分析

1. 邻接表g：存储n-1条双向边 → O(n)

2. dep、timeIn、timeOut、pathXorFromRoot、t数组：均长度n → O(n)

3. 倍增祖先表pa：n × logn（logn固定16） → O(n logn)

4. 异或树状数组fenwick：长度n+1 → O(n)

5. 答案数组ans：最多q个布尔值 → O(q)

总额外空间复杂度

O(n logn + q)
主导项为倍增表n logn，q与n同量级，实际可简化描述为O(n logn)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
    "strconv"
    "strings"
)

 type fenwick []int

 func newFenwickTree(n int) fenwick {
    returnmake(fenwick, n+1) // 使用下标 1 到 n
}

 // a[i] ^= val
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) update(i int, val int) {
    for ; i < len(f); i += i & -i {
        f[i] ^= val
    }
}

 // 计算前缀异或和 a[1] ^ ... ^ a[i]
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) pre(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res ^= f[i]
    }
    return
}

 func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) {
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

     mx := bits.Len(uint(n))
    pa := make([][16]int, n)
    dep := make([]int, n)
    timeIn := make([]int, n) // DFS 时间戳
    timeOut := make([]int, n)
    clock := 0
    pathXorFromRoot := make([]int, n) // 从根开始的路径中的字母奇偶性的集合
    pathXorFromRoot[0] = 1 << (s[0] - 'a')

     var dfs func(int, int)
    dfs = func(x, p int) {
        pa[x][0] = p
        clock++
        timeIn[x] = clock
        for _, y := range g[x] {
            if y != p {
                dep[y] = dep[x] + 1
                pathXorFromRoot[y] = pathXorFromRoot[x] ^ 1<<(s[y]-'a')
                dfs(y, x)
            }
        }
        timeOut[x] = clock
    }
    dfs(0, -1)

     for i := range mx - 1 {
        for x := range pa {
            p := pa[x][i]
            if p != -1 {
                pa[x][i+1] = pa[p][i]
            } else {
                pa[x][i+1] = -1
            }
        }
    }

     uptoDep := func(x, d int)int {
        for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
            x = pa[x][bits.TrailingZeros32(k)]
        }
        return x
    }

     // 返回 x 和 y 的最近公共祖先
    getLCA := func(x, y int)int {
        if dep[x] > dep[y] {
            x, y = y, x
        }
        y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
        if y == x {
            return x
        }
        for i := mx - 1; i >= 0; i-- {
            px, py := pa[x][i], pa[y][i]
            if px != py {
                x, y = px, py // 同时往上跳 2^i 步
            }
        }
        return pa[x][0]
    }

     // 上面全是模板，下面开始本题逻辑

     t := []byte(s)
    f := newFenwickTree(n) // 注意树状数组是异或运算
    for _, q := range queries {
        if q[0] == 'u' {
            x, _ := strconv.Atoi(q[7 : len(q)-2])
            c := q[len(q)-1]
            val := 1<<(t[x]-'a') ^ 1<<(c-'a') // 擦除旧的，换上新的
            t[x] = c
            // 子树 x 全部异或 val，转换成对区间 [timeIn[x], timeOut[x]] 的差分更新
            f.update(timeIn[x], val)
            f.update(timeOut[x]+1, val)
        } else {
            q = q[6:]
            i := strings.IndexByte(q, ' ')
            x, _ := strconv.Atoi(q[:i])
            y, _ := strconv.Atoi(q[i+1:])
            lca := getLCA(x, y)
            res := pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1<<(t[lca]-'a')
            ans = append(ans, res&(res-1) == 0) // 至多一个字母的出现次数是奇数
        }
    }
    return
}

 func main() {
    n := 3
    edges := [][]int{{0, 1}, {1, 2}}
    s := "aac"
    queries := []string{"query 0 2", "update 1 b", "query 0 2"}
    result := palindromePath(n, edges, s, queries)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import sys
from typing import List

 def palindromePath(n: int, edges: List[List[int]], s: str, queries: List[str]) -> List[bool]:
    # 建图
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)

     # 二进制提升的层数
    mx = n.bit_length()
    pa = [[-1] * mx for _ in range(n)]
    dep = [0] * n
    time_in = [0] * n
    time_out = [0] * n
    path_xor = [0] * n  # 从根到当前节点的路径异或值
    path_xor[0] = 1 << (ord(s[0]) - 97)

     clock = 0
    # 递归可能会很深，提高递归深度限制
    sys.setrecursionlimit(300000)

     def dfs(x: int, p: int):
        nonlocal clock
        pa[x][0] = p
        clock += 1
        time_in[x] = clock
        for y in g[x]:
            if y != p:
                dep[y] = dep[x] + 1
                path_xor[y] = path_xor[x] ^ (1 << (ord(s[y]) - 97))
                dfs(y, x)
        time_out[x] = clock

     dfs(0, -1)

     # 建立倍增表
    for i in range(mx - 1):
        for x in range(n):
            p = pa[x][i]
            if p != -1:
                pa[x][i + 1] = pa[p][i]
            else:
                pa[x][i + 1] = -1

     def upto_dep(x: int, d: int) -> int:
        # 将节点 x 提升到深度 d
        diff = dep[x] - d
        while diff > 0:
            lsb = diff & -diff
            step = (lsb.bit_length() - 1)  # 最低位 1 的位置
            x = pa[x][step]
            diff ^= lsb  # diff -= lsb 也可以
        return x

     def get_lca(x: int, y: int) -> int:
        if dep[x] > dep[y]:
            x, y = y, x
        y = upto_dep(y, dep[x])  # 提升到同一深度
        if y == x:
            return x
        for i in range(mx - 1, -1, -1):
            px, py = pa[x][i], pa[y][i]
            if px != py:
                x, y = px, py
        return pa[x][0]

     # 树状数组（异或版本）
    class Fenwick:
        def __init__(self, size: int):
            self.tree = [0] * (size + 1)  # 下标 1..size

         def update(self, i: int, val: int):
            while i < len(self.tree):
                self.tree[i] ^= val
                i += i & -i

         def pre(self, i: int) -> int:
            res = 0
            while i > 0:
                res ^= self.tree[i]
                i &= i - 1
            return res

     t = list(s)  # 可变字符串
    bit = Fenwick(n)  # 最多用到 time_out[x]+1，time_out 最大为 n，因此 n 足够（实际上需要 n+1 大小，用 n+2 更安全）
    # 为安全起见，可以扩大一点
    bit = Fenwick(n + 5)

     ans = []
    for q in queries:
        if q.startswith('u'):      # update
            parts = q.split()
            x = int(parts[1])
            c = parts[2]
            old = t[x]
            val = (1 << (ord(old) - 97)) ^ (1 << (ord(c) - 97))
            t[x] = c
            # 子树区间差分更新
            bit.update(time_in[x], val)
            bit.update(time_out[x] + 1, val)
        else:                      # query
            parts = q.split()
            x = int(parts[1])
            y = int(parts[2])
            lca = get_lca(x, y)
            res = (path_xor[x] ^ path_xor[y] ^
                   bit.pre(time_in[x]) ^ bit.pre(time_in[y]) ^
                   (1 << (ord(t[lca]) - 97)))
            ans.append(res & (res - 1) == 0)  # 至多一个字母出现奇数次

     return ans

 if __name__ == "__main__":
    n = 3
    edges = [[0, 1], [1, 2]]
    s = "aac"
    queries = ["query 0 2", "update 1 b", "query 0 2"]
    result = palindromePath(n, edges, s, queries)
    print(result)  

C++完整代码如下：

  

  

  

  

using namespace std;

 // 树状数组（异或版本）
class Fenwick {
    vector tree;
    int n;
public:
    Fenwick(int size) : n(size), tree(size + 1) {} // 下标 1..n

     // a[i] ^= val, 1 <= i <= n
    void update(int i, int val) {
        while (i <= n) {
            tree[i] ^= val;
            i += i & -i;
        }
    }

     // 前缀异或和 a[1]^...^a[i], 1 <= i <= n
    int pre(int i) {
        int res = 0;
        while (i > 0) {
            res ^= tree[i];
            i &= i - 1;
        }
        return res;
    }
};

 vector palindromePath(int n, vector 
 
 int 
 >>& edges,  
 string 
  s, vector< 
 string 
 >& queries) { 
 
 
      
 // 建图 
 
 
     vector 
 
 int 
 >> g(n); 
 
 
      
 for 
  (auto& e : edges) { 
 
 
          
 int 
  x = e[ 
 0 
 ], y = e[ 
 1 
 ]; 
 
 
         g[x].push_back(y); 
 
 
         g[y].push_back(x); 
 
 
     } 
 
 
 
 
      
 // 倍增层数 
 
 
      
 int 
  mx =  
 0 
 ; 
 
 
     while (( 
 1 
  << mx) < n) ++mx; 
 
 
      
 if 
  (mx ==  
 0 
 ) mx =  
 1 
 ;  
 // 至少保证 1 层 
 
 
 
 
     vector 
 
 int 
 >> pa(n, vector< 
 int 
 >(mx,  
 -1 
 )); 
 
 
     vector< 
 int 
 > dep(n,  
 0 
 ); 
 
 
     vector< 
 int 
 > timeIn(n), timeOut(n); 
 
 
      
 int 
  clock =  
 0 
 ; 
 
 
     vector< 
 int 
 > pathXorFromRoot(n,  
 0 
 ); 
 
 
     pathXorFromRoot[ 
 0 
 ] =  
 1 
  << (s[ 
 0 
 ] -  
 'a' 
 ); 
 
 
 
 
      
 // DFS 递归函数 
 
 
     function 
 
 int 
 ,  
 int 
 )> dfs = [&]( 
 int 
  x,  
 int 
  p) { 
 
 
         pa[x][ 
 0 
 ] = p; 
 
 
         ++clock; 
 
 
         timeIn[x] = clock; 
 
 
          
 for 
  ( 
 int 
  y : g[x]) { 
 
 
              
 if 
  (y != p) { 
 
 
                 dep[y] = dep[x] +  
 1 
 ; 
 
 
                 pathXorFromRoot[y] = pathXorFromRoot[x] ^ ( 
 1 
  << (s[y] -  
 'a' 
 )); 
 
 
                 dfs(y, x); 
 
 
             } 
 
 
         } 
 
 
         timeOut[x] = clock; 
 
 
     }; 
 
 
     dfs( 
 0 
 ,  
 -1 
 ); 
 
 
 
 
      
 // 建立倍增表 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < mx -  
 1 
 ; ++i) { 
 
 
          
 for 
  ( 
 int 
  x =  
 0 
 ; x < n; ++x) { 
 
 
              
 int 
  p = pa[x][i]; 
 
 
              
 if 
  (p !=  
 -1 
 ) 
 
 
                 pa[x][i +  
 1 
 ] = pa[p][i]; 
 
 
              
 else 
 
 
                 pa[x][i +  
 1 
 ] =  
 -1 
 ; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // 提升到指定深度 
 
 
     auto uptoDep = [&]( 
 int 
  x,  
 int 
  d) { 
 
 
          
 int 
  diff = dep[x] - d; 
 
 
         while (diff >  
 0 
 ) { 
 
 
              
 int 
  lsb = diff & -diff; 
 
 
              
 int 
  step = __builtin_ctz(lsb); 
 
 
             x = pa[x][step]; 
 
 
             diff &= diff -  
 1 
 ;  
 // diff -= lsb 
 
 
         } 
 
 
          
 return 
  x; 
 
 
     }; 
 
 
 
 
      
 // 最近公共祖先 
 
 
     auto getLCA = [&]( 
 int 
  x,  
 int 
  y) { 
 
 
          
 if 
  (dep[x] > dep[y]) swap(x, y); 
 
 
         y = uptoDep(y, dep[x]); 
 
 
          
 if 
  (y == x)  
 return 
  x; 
 
 
          
 for 
  ( 
 int 
  i = mx -  
 1 
 ; i >=  
 0 
 ; --i) { 
 
 
              
 int 
  px = pa[x][i], py = pa[y][i]; 
 
 
              
 if 
  (px != py) { 
 
 
                 x = px; 
 
 
                 y = py; 
 
 
             } 
 
 
         } 
 
 
          
 return 
  pa[x][ 
 0 
 ]; 
 
 
     }; 
 
 
 
 
      
 string 
  t = s;  
 // 可变字符数组 
 
 
     Fenwick bit(n);  
 // 树状数组长度 n，下标 1..n 
 
 
     vector< 
 bool 
 > ans; 
 
 
 
 
      
 for 
  (auto& q : queries) { 
 
 
          
 if 
  (q[ 
 0 
 ] ==  
 'u' 
 ) {  
 // update 
 
 
              
 int 
  x; char c; 
 
 
             sscanf(q.c_str(),  
 "update %d %c" 
 , &x, &c); 
 
 
             char old = t[x]; 
 
 
              
 int 
  val = ( 
 1 
  << (old -  
 'a' 
 )) ^ ( 
 1 
  << (c -  
 'a' 
 )); 
 
 
             t[x] = c; 
 
 
              
 // 子树区间差分 
 
 
             bit.update(timeIn[x], val); 
 
 
             bit.update(timeOut[x] +  
 1 
 , val); 
 
 
         }  
 else 
  {  
 // query 
 
 
              
 int 
  x, y; 
 
 
             sscanf(q.c_str(),  
 "query %d %d" 
 , &x, &y); 
 
 
              
 int 
  lca = getLCA(x, y); 
 
 
              
 int 
  res = pathXorFromRoot[x] ^ pathXorFromRoot[y] 
 
 
                       ^ bit.pre(timeIn[x]) ^ bit.pre(timeIn[y]) 
 
 
                       ^ ( 
 1 
  << (t[lca] -  
 'a' 
 )); 
 
 
             ans.push_back((res & (res -  
 1 
 )) ==  
 0 
 ); 
 
 
         } 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 3 
 ; 
 
 
     vector 
 
 int 
 >> edges = {{ 
 0 
 ,  
 1 
 }, { 
 1 
 ,  
 2 
 }}; 
 
 
      
 string 
  s =  
 "aac" 
 ; 
 
 
     vector< 
 string 
 > queries = { 
 "query 0 2" 
 ,  
 "update 1 b" 
 ,  
 "query 0 2" 
 }; 
 
 
     vector< 
 bool 
 > result = palindromePath(n, edges, s, queries); 
 
 
 
 
      
 // 输出结果 
 
 
     cout <<  
 "[" 
 ; 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); ++i) { 
 
 
          
 if 
  (i >  
 0 
 ) cout <<  
 ", " 
 ; 
 
 
         cout << (result[i] ?  
 "true" 
  :  
 "false" 
 ); 
 
 
     } 
 
 
     cout <<  
 "]" 
  << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。