3841. Palindromic Path Queries in a Tree

/**
 * Problem: LeetCode 3841 - Palindromic Path Queries in a Tree
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

/**
 * Problem: LeetCode 3841 - Palindromic Path Queries in a Tree
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    int[] bit;
    int n;

    private void upd(int i, int v) {
        for (; i <= n + 1; i += i & -i) bit[i] ^= v;
    }

    private int qry(int i) {
        int r = 0;
        for (; i > 0; i -= i & -i) r ^= bit[i];
        return r;
    }

    public List<Boolean> palindromePath(int n, int[][] edges, String s, String[] queries) {
        this.n = n;
        bit = new int[n + 3];

        // Flat adjacency list for optimal cache locality
        int[] head = new int[n], nxt = new int[2 * (n - 1)], to = new int[2 * (n - 1)];
        Arrays.fill(head, -1);
        int ec = 0;
        for (int[] e : edges) {
            to[ec] = e[1]; nxt[ec] = head[e[0]]; head[e[0]] = ec++;
            to[ec] = e[0]; nxt[ec] = head[e[1]]; head[e[1]] = ec++;
        }

        char[] arr = s.toCharArray();
        int LOG = 17;
        int[][] up = new int[LOG][n];
        int[] depth = new int[n], tin = new int[n], tout = new int[n], base = new int[n];
        int[] parent = new int[n];
        int[] ptr = head.clone();
        int[] stack = new int[n];
        int top = 0, timer = 0;

        // Iterative Euler Tour DFS (Zero StackOverflow risk)
        stack[top++] = 0;
        parent[0] = -1;
        up[0][0] = 0;
        tin[0] = ++timer;
        base[0] = 1 << (arr[0] - 'a');

        while (top > 0) {
            int u = stack[top - 1];
            if (ptr[u] != -1) {
                int e = ptr[u];
                ptr[u] = nxt[e];
                int v = to[e];
                if (v == parent[u]) continue;
                parent[v] = u;
                depth[v] = depth[u] + 1;
                base[v] = base[u] ^ (1 << (arr[v] - 'a'));
                up[0][v] = u;
                tin[v] = ++timer;
                stack[top++] = v;
            } else {
                tout[u] = timer;
                top--;
            }
        }

        // Binary Lifting Table
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }

        List<Boolean> ans = new ArrayList<>(queries.length);

        for (String q : queries) {
            String[] parts = q.split(" ");
            if (parts[0].equals("update")) {
                int u = Integer.parseInt(parts[1]);
                char c = parts[2].charAt(0);
                if (arr[u] == c) continue;
                int d = (1 << (arr[u] - 'a')) ^ (1 << (c - 'a'));
                upd(tin[u], d);
                upd(tout[u] + 1, d);
                arr[u] = c;
            } else {
                int u = Integer.parseInt(parts[1]);
                int v = Integer.parseInt(parts[2]);

                // Binary Lifting LCA
                int a = u, b = v;
                if (depth[a] < depth[b]) { int t = a; a = b; b = t; }
                int diff = depth[a] - depth[b];
                for (int k = 0; k < LOG; k++) {
                    if (((diff >> k) & 1) == 1) a = up[k][a];
                }
                int lca;
                if (a == b) {
                    lca = a;
                } else {
                    for (int k = LOG - 1; k >= 0; k--) {
                        if (up[k][a] != up[k][b]) {
                            a = up[k][a];
                            b = up[k][b];
                        }
                    }
                    lca = up[0][a];
                }

                int pu = base[u] ^ qry(tin[u]);
                int pv = base[v] ^ qry(tin[v]);
                int mask = pu ^ pv ^ (1 << (arr[lca] - 'a'));

                ans.add((mask & (mask - 1)) == 0);
            }
        }

        return ans;
    }
}

"""
Problem: LeetCode 3841 - Palindromic Path Queries in a Tree
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def palindromePath(self, n: int, edges: List[List[int]], s: str, queries: List[str]) -> List[bool]:
        # Adjacency list
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        arr = list(s)
        LOG = 17
        up = [[0] * n for _ in range(LOG)]
        depth = [0] * n
        tin = [0] * n
        tout = [0] * n
        base = [0] * n

        # Iterative Euler Tour DFS (Zero StackOverflow risk)
        timer = 0
        parent = [-1] * n
        it = [0] * n
        order = [0]
        timer += 1
        tin[0] = timer
        base[0] = 1 << (ord(arr[0]) - ord('a'))

        while order:
            u = order[-1]
            if it[u] < len(adj[u]):
                v = adj[u][it[u]]
                it[u] += 1
                if v == parent[u]:
                    continue
                parent[v] = u
                depth[v] = depth[u] + 1
                base[v] = base[u] ^ (1 << (ord(arr[v]) - ord('a')))
                up[0][v] = u
                timer += 1
                tin[v] = timer
                order.append(v)
            else:
                tout[u] = timer
                order.pop()

        # Binary Lifting Table
        for k in range(1, LOG):
            for v in range(n):
                up[k][v] = up[k - 1][up[k - 1][v]]

        # Fenwick Tree for range XOR updates and point queries
        bit = [0] * (n + 3)

        def upd(i: int, v: int) -> None:
            while i <= n + 1:
                bit[i] ^= v
                i += i & (-i)

        def qry(i: int) -> int:
            r = 0
            while i > 0:
                r ^= bit[i]
                i -= i & (-i)
            return r

        ans = []
        for q in queries:
            parts = q.split()
            if parts[0] == "update":
                u = int(parts[1])
                c = parts[2]
                if arr[u] == c:
                    continue
                d = (1 << (ord(arr[u]) - ord('a'))) ^ (1 << (ord(c) - ord('a')))
                upd(tin[u], d)
                upd(tout[u] + 1, d)
                arr[u] = c
            else:
                u = int(parts[1])
                v = int(parts[2])

                # Binary Lifting LCA
                a, b = u, v
                if depth[a] < depth[b]:
                    a, b = b, a
                diff = depth[a] - depth[b]
                for k in range(LOG):
                    if (diff >> k) & 1:
                        a = up[k][a]

                if a == b:
                    lca = a
                else:
                    for k in range(LOG - 1, -1, -1):
                        if up[k][a] != up[k][b]:
                            a = up[k][a]
                            b = up[k][b]
                    lca = up[0][a]

                pu = base[u] ^ qry(tin[u])
                pv = base[v] ^ qry(tin[v])
                mask = pu ^ pv ^ (1 << (ord(arr[lca]) - ord('a')))

                ans.append((mask & (mask - 1)) == 0)

        return ans

/**
 * Problem: LeetCode 3841 - Palindromic Path Queries in a Tree
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

class Solution {
    vector<int> bit;
    int n;

    void upd(int i, int v) {
        for (; i <= n + 1; i += i & -i) bit[i] ^= v;
    }

    int qry(int i) {
        int r = 0;
        for (; i > 0; i -= i & -i) r ^= bit[i];
        return r;
    }

public:
    vector<bool> palindromePath(int n, vector<vector<int>>& edges, string s, vector<string>& queries) {
        this->n = n;
        bit.assign(n + 3, 0);

        // Flat adjacency list for optimal cache locality
        vector<int> head(n, -1), nxt(2 * (n - 1)), to(2 * (n - 1));
        int ec = 0;
        for (const auto& e : edges) {
            to[ec] = e[1]; nxt[ec] = head[e[0]]; head[e[0]] = ec++;
            to[ec] = e[0]; nxt[ec] = head[e[1]]; head[e[1]] = ec++;
        }

        const int LOG = 17;
        vector<vector<int>> up(LOG, vector<int>(n, 0));
        vector<int> depth(n, 0), tin(n, 0), tout(n, 0), base(n, 0);
        vector<int> parent(n, -1);
        vector<int> ptr = head;
        vector<int> st(n);
        int top = 0, timer = 0;

        // Iterative Euler Tour DFS (Zero StackOverflow risk)
        st[top++] = 0;
        parent[0] = -1;
        up[0][0] = 0;
        tin[0] = ++timer;
        base[0] = 1 << (s[0] - 'a');

        while (top > 0) {
            int u = st[top - 1];
            if (ptr[u] != -1) {
                int e = ptr[u];
                ptr[u] = nxt[e];
                int v = to[e];
                if (v == parent[u]) continue;
                parent[v] = u;
                depth[v] = depth[u] + 1;
                base[v] = base[u] ^ (1 << (s[v] - 'a'));
                up[0][v] = u;
                tin[v] = ++timer;
                st[top++] = v;
            } else {
                tout[u] = timer;
                top--;
            }
        }

        // Binary Lifting Table
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }

        vector<bool> ans;
        ans.reserve(queries.size());

        for (const string& q : queries) {
            stringstream ss(q);
            string type;
            ss >> type;
            if (type == "update") {
                int u;
                char c;
                ss >> u >> c;
                if (s[u] == c) continue;
                int d = (1 << (s[u] - 'a')) ^ (1 << (c - 'a'));
                upd(tin[u], d);
                upd(tout[u] + 1, d);
                s[u] = c;
            } else {
                int u, v;
                ss >> u >> v;

                // Binary Lifting LCA
                int a = u, b = v;
                if (depth[a] < depth[b]) swap(a, b);
                int diff = depth[a] - depth[b];
                for (int k = 0; k < LOG; k++) {
                    if ((diff >> k) & 1) a = up[k][a];
                }

                int lca;
                if (a == b) {
                    lca = a;
                } else {
                    for (int k = LOG - 1; k >= 0; k--) {
                        if (up[k][a] != up[k][b]) {
                            a = up[k][a];
                            b = up[k][b];
                        }
                    }
                    lca = up[0][a];
                }

                int pu = base[u] ^ qry(tin[u]);
                int pv = base[v] ^ qry(tin[v]);
                int mask = pu ^ pv ^ (1 << (s[lca] - 'a'));

                ans.push_back((mask & (mask - 1)) == 0);
            }
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 3841 - Palindromic Path Queries in a Tree
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var palindromePath = function(n, edges, s, queries) {
    const bit = new Int32Array(n + 3);

    function upd(i, v) {
        for (; i <= n + 1; i += i & -i) bit[i] ^= v;
    }

    function qry(i) {
        let r = 0;
        for (; i > 0; i -= i & -i) r ^= bit[i];
        return r;
    }

    // Flat adjacency list for optimal cache locality
    const head = new Int32Array(n).fill(-1);
    const nxt = new Int32Array(2 * (n - 1));
    const to = new Int32Array(2 * (n - 1));
    let ec = 0;

    for (let i = 0; i < edges.length; i++) {
        const u = edges[i][0];
        const v = edges[i][1];
        to[ec] = v; nxt[ec] = head[u]; head[u] = ec++;
        to[ec] = u; nxt[ec] = head[v]; head[v] = ec++;
    }

    const arr = s.split('');
    const LOG = 17;
    const up = Array.from({ length: LOG }, () => new Int32Array(n));
    const depth = new Int32Array(n);
    const tin = new Int32Array(n);
    const tout = new Int32Array(n);
    const base = new Int32Array(n);
    const parent = new Int32Array(n);
    const ptr = head.slice();
    const stack = new Int32Array(n);
    let top = 0;
    let timer = 0;

    // Iterative Euler Tour DFS (Zero StackOverflow risk)
    stack[top++] = 0;
    parent[0] = -1;
    up[0][0] = 0;
    tin[0] = ++timer;
    base[0] = 1 << (arr[0].charCodeAt(0) - 97);

    while (top > 0) {
        const u = stack[top - 1];
        if (ptr[u] !== -1) {
            const e = ptr[u];
            ptr[u] = nxt[e];
            const v = to[e];
            if (v === parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            base[v] = base[u] ^ (1 << (arr[v].charCodeAt(0) - 97));
            up[0][v] = u;
            tin[v] = ++timer;
            stack[top++] = v;
        } else {
            tout[u] = timer;
            top--;
        }
    }

    // Binary Lifting Table
    for (let k = 1; k < LOG; k++) {
        for (let v = 0; v < n; v++) {
            up[k][v] = up[k - 1][up[k - 1][v]];
        }
    }

    const ans = [];

    for (let i = 0; i < queries.length; i++) {
        const parts = queries[i].split(' ');
        if (parts[0] === 'update') {
            const u = Number(parts[1]);
            const c = parts[2];
            if (arr[u] === c) continue;
            const d = (1 << (arr[u].charCodeAt(0) - 97)) ^ (1 << (c.charCodeAt(0) - 97));
            upd(tin[u], d);
            upd(tout[u] + 1, d);
            arr[u] = c;
        } else {
            let a = Number(parts[1]);
            let b = Number(parts[2]);

            // Binary Lifting LCA
            if (depth[a] < depth[b]) {
                const t = a; a = b; b = t;
            }
            const diff = depth[a] - depth[b];
            for (let k = 0; k < LOG; k++) {
                if ((diff >> k) & 1) a = up[k][a];
            }

            let lca;
            if (a === b) {
                lca = a;
            } else {
                for (let k = LOG - 1; k >= 0; k--) {
                    if (up[k][a] !== up[k][b]) {
                        a = up[k][a];
                        b = up[k][b];
                    }
                }
                lca = up[0][a];
            }

            const pu = base[Number(parts[1])] ^ qry(tin[Number(parts[1])]);
            const pv = base[Number(parts[2])] ^ qry(tin[Number(parts[2])]);
            const mask = pu ^ pv ^ (1 << (arr[lca].charCodeAt(0) - 97));

            ans.push((mask & (mask - 1)) === 0);
        }
    }

    return ans;
};