LeetCode Problem 3841

Difficulty: 🔴 Hard
Topics: Array, String, Divide and Conquer, Tree, Segment Tree

Solution

LeetCode 3841: Palindromic Path Queries in a Tree

Problem Understanding

We are given a tree with n nodes. Each node stores a lowercase English letter. The tree is undirected and connected, so there is exactly one simple path between any two nodes.

The problem supports two kinds of operations:

1. Update

Change the character assigned to a node. 2. Query

Consider the unique path between nodes u and v. Collect all characters along that path. Determine whether those characters can be rearranged into a palindrome.

A string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. For example:

• "aac" → frequencies {a:2, c:1} → one odd frequency → palindrome possible.
• "abc" → frequencies {a:1, b:1, c:1} → three odd frequencies → palindrome impossible.

The tree contains up to 5 * 10^4 nodes and there are up to 5 * 10^4 operations. This immediately rules out any solution that traverses an entire path for every query, because a path can contain O(n) nodes.

The key challenge is therefore supporting:

• Point updates on node characters.
• Path frequency queries.
• Fast enough performance for 50,000 operations.

Important edge cases include:

• A path consisting of a single node.
• Updates that assign the same character already present.
• Long chain trees where path lengths become O(n).
• Star-shaped trees where many paths pass through the root.
• Multiple updates to the same node before later queries.
• Paths whose Lowest Common Ancestor (LCA) is one of the endpoints.

The input guarantees that the graph is a valid tree, so every pair of nodes has exactly one simple path.

Approaches

Brute Force

For every query:

1. Find the path from u to v.
2. Traverse every node on that path.
3. Count character frequencies.
4. Check whether at most one frequency is odd.

For updates, simply modify the stored character.

This approach is correct because it explicitly computes the exact path and exact frequency counts. However, a path can contain O(n) nodes, and finding the path itself may also require O(n) work.

With up to 5 * 10^4 queries, the worst case becomes roughly:

O(n * q)

which is far too slow.

Key Observation

For palindrome rearrangement, we do not need the exact frequency of each character.

We only need to know which characters occur an odd number of times.

Since there are only 26 lowercase letters, we can represent parity using a 26-bit mask:

• Bit i = 1 if character i appears an odd number of times.
• Bit i = 0 if character i appears an even number of times.

A path can form a palindrome iff the resulting mask contains at most one set bit.

Therefore, each node contributes a single bit:

mask(node) = 1 << (s[node] - 'a')

The path query becomes an XOR aggregation problem.

To support:

• point updates,
• path XOR queries,

we use Heavy-Light Decomposition (HLD) combined with a segment tree.

HLD converts a tree path query into O(log n) contiguous segment queries. Each segment query is answered by a segment tree in O(log n).

Thus each operation costs O(log² n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(qn)	O(n)	Traverse entire path for every query
Optimal	O((n + q) log² n)	O(n)	Heavy-Light Decomposition + Segment Tree

Algorithm Walkthrough

Step 1: Build the tree

Construct the adjacency list from the edge list.

This allows efficient DFS traversals and HLD preprocessing.

Step 2: Compute subtree sizes and heavy children

Perform a DFS from node 0.

For every node compute:

• parent
• depth
• subtree size
• heavy child

The heavy child is the child with the largest subtree.

Heavy edges help keep the number of chain transitions small.

Step 3: Decompose the tree

Perform a second DFS.

Assign every node:

• head[node] = head of its heavy chain
• pos[node] = position in the linearized array

The decomposition converts the tree into an array where every heavy chain becomes a contiguous interval.

Step 4: Build the segment tree

For each node:

value[node] = 1 << (character index)

Store these values in HLD order.

Build a segment tree whose operation is XOR.

Step 5: Handle updates

Suppose node u changes from character x to character y.

Compute:

new_mask = 1 << (y - 'a')

Update position:

pos[u]

inside the segment tree.

Step 6: Handle path queries

To query path (u, v):

While the two nodes belong to different chains:

1. Move the deeper chain upward.
2. XOR the segment corresponding to that chain.

Once both nodes are in the same chain:

1. Query the remaining interval.
2. XOR into the answer.

The final XOR mask represents parity counts for all characters on the path.

Step 7: Check palindrome condition

Let the resulting mask be m.

A palindrome rearrangement is possible iff:

m == 0

or

m has exactly one set bit

which can be tested using:

m & (m - 1) == 0

Why it works

Each node contributes one bit corresponding to its character. XOR naturally tracks parity because:

• odd occurrences leave the bit set,
• even occurrences cancel out.

Heavy-Light Decomposition breaks any tree path into at most O(log n) chain segments. The segment tree computes XOR over each segment efficiently. Therefore the computed mask exactly represents the parity of every character along the path. A string can be rearranged into a palindrome precisely when at most one character has odd frequency, which corresponds to at most one set bit in the mask.

Python Solution

from typing import List

class Solution:
    def palindromePath(
        self,
        n: int,
        edges: List[List[int]],
        s: str,
        queries: List[str]
    ) -> List[bool]:

        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        parent = [-1] * n
        depth = [0] * n
        size = [0] * n
        heavy = [-1] * n

        def dfs(u: int, p: int) -> int:
            parent[u] = p
            size[u] = 1

            max_subtree = 0

            for nxt in graph[u]:
                if nxt == p:
                    continue

                depth[nxt] = depth[u] + 1
                dfs(nxt, u)

                size[u] += size[nxt]

                if size[nxt] > max_subtree:
                    max_subtree = size[nxt]
                    heavy[u] = nxt

            return size[u]

        dfs(0, -1)

        head = [0] * n
        pos = [0] * n
        current_pos = 0

        def decompose(u: int, h: int) -> None:
            nonlocal current_pos

            head[u] = h
            pos[u] = current_pos
            current_pos += 1

            if heavy[u] != -1:
                decompose(heavy[u], h)

            for nxt in graph[u]:
                if nxt == parent[u] or nxt == heavy[u]:
                    continue
                decompose(nxt, nxt)

        decompose(0, 0)

        base = [0] * n
        chars = list(s)

        for node in range(n):
            base[pos[node]] = 1 << (ord(chars[node]) - ord("a"))

        seg = [0] * (4 * n)

        def build(idx: int, left: int, right: int) -> None:
            if left == right:
                seg[idx] = base[left]
                return

            mid = (left + right) // 2

            build(idx * 2, left, mid)
            build(idx * 2 + 1, mid + 1, right)

            seg[idx] = seg[idx * 2] ^ seg[idx * 2 + 1]

        def update(
            idx: int,
            left: int,
            right: int,
            target: int,
            value: int
        ) -> None:
            if left == right:
                seg[idx] = value
                return

            mid = (left + right) // 2

            if target <= mid:
                update(idx * 2, left, mid, target, value)
            else:
                update(idx * 2 + 1, mid + 1, right, target, value)

            seg[idx] = seg[idx * 2] ^ seg[idx * 2 + 1]

        def query(
            idx: int,
            left: int,
            right: int,
            ql: int,
            qr: int
        ) -> int:
            if ql <= left and right <= qr:
                return seg[idx]

            if right < ql or qr < left:
                return 0

            mid = (left + right) // 2

            return (
                query(idx * 2, left, mid, ql, qr)
                ^ query(idx * 2 + 1, mid + 1, right, ql, qr)
            )

        build(1, 0, n - 1)

        def path_xor(u: int, v: int) -> int:
            result = 0

            while head[u] != head[v]:
                if depth[head[u]] < depth[head[v]]:
                    u, v = v, u

                result ^= query(
                    1,
                    0,
                    n - 1,
                    pos[head[u]],
                    pos[u]
                )

                u = parent[head[u]]

            if depth[u] > depth[v]:
                u, v = v, u

            result ^= query(
                1,
                0,
                n - 1,
                pos[u],
                pos[v]
            )

            return result

        answer = []

        for operation in queries:
            parts = operation.split()

            if parts[0] == "update":
                node = int(parts[1])
                ch = parts[2]

                chars[node] = ch

                mask = 1 << (ord(ch) - ord("a"))

                update(
                    1,
                    0,
                    n - 1,
                    pos[node],
                    mask
                )

            else:
                u = int(parts[1])
                v = int(parts[2])

                mask = path_xor(u, v)

                answer.append(mask == 0 or (mask & (mask - 1)) == 0)

        return answer

Implementation Explanation

The first DFS computes subtree sizes and identifies heavy children. The second DFS performs Heavy-Light Decomposition and assigns every node a position in a linear array.

Each node stores a 26-bit mask with exactly one bit set. The segment tree stores XOR values over intervals of the HLD array.

The path_xor() function performs a standard HLD path query. While the two nodes belong to different chains, it repeatedly takes the deeper chain segment and XORs its contribution. Once both nodes are in the same chain, one final segment query completes the path.

Updates modify a single position in the segment tree. Queries compute the path mask and test whether at most one bit remains set.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func palindromePath(n int, edges [][]int, s string, queries []string) []bool {
	graph := make([][]int, n)

	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	parent := make([]int, n)
	depth := make([]int, n)
	size := make([]int, n)
	heavy := make([]int, n)

	for i := range heavy {
		heavy[i] = -1
	}

	var dfs func(int, int)

	dfs = func(u, p int) {
		parent[u] = p
		size[u] = 1

		maxSubtree := 0

		for _, nxt := range graph[u] {
			if nxt == p {
				continue
			}

			depth[nxt] = depth[u] + 1
			dfs(nxt, u)

			size[u] += size[nxt]

			if size[nxt] > maxSubtree {
				maxSubtree = size[nxt]
				heavy[u] = nxt
			}
		}
	}

	dfs(0, -1)

	head := make([]int, n)
	pos := make([]int, n)

	curPos := 0

	var decompose func(int, int)

	decompose = func(u, h int) {
		head[u] = h
		pos[u] = curPos
		curPos++

		if heavy[u] != -1 {
			decompose(heavy[u], h)
		}

		for _, nxt := range graph[u] {
			if nxt == parent[u] || nxt == heavy[u] {
				continue
			}
			decompose(nxt, nxt)
		}
	}

	decompose(0, 0)

	base := make([]int, n)
	chars := []byte(s)

	for i := 0; i < n; i++ {
		base[pos[i]] = 1 << (chars[i] - 'a')
	}

	seg := make([]int, 4*n)

	var build func(int, int, int)

	build = func(idx, l, r int) {
		if l == r {
			seg[idx] = base[l]
			return
		}

		mid := (l + r) / 2

		build(idx*2, l, mid)
		build(idx*2+1, mid+1, r)

		seg[idx] = seg[idx*2] ^ seg[idx*2+1]
	}

	build(1, 0, n-1)

	var update func(int, int, int, int, int)

	update = func(idx, l, r, target, value int) {
		if l == r {
			seg[idx] = value
			return
		}

		mid := (l + r) / 2

		if target <= mid {
			update(idx*2, l, mid, target, value)
		} else {
			update(idx*2+1, mid+1, r, target, value)
		}

		seg[idx] = seg[idx*2] ^ seg[idx*2+1]
	}

	var query func(int, int, int, int, int) int

	query = func(idx, l, r, ql, qr int) int {
		if ql <= l && r <= qr {
			return seg[idx]
		}

		if r < ql || qr < l {
			return 0
		}

		mid := (l + r) / 2

		return query(idx*2, l, mid, ql, qr) ^
			query(idx*2+1, mid+1, r, ql, qr)
	}

	pathXor := func(u, v int) int {
		result := 0

		for head[u] != head[v] {
			if depth[head[u]] < depth[head[v]] {
				u, v = v, u
			}

			result ^= query(
				1,
				0,
				n-1,
				pos[head[u]],
				pos[u],
			)

			u = parent[head[u]]
		}

		if depth[u] > depth[v] {
			u, v = v, u
		}

		result ^= query(
			1,
			0,
			n-1,
			pos[u],
			pos[v],
		)

		return result
	}

	ans := []bool{}

	for _, op := range queries {
		parts := strings.Split(op, " ")

		if parts[0] == "update" {
			node, _ := strconv.Atoi(parts[1])
			ch := parts[2][0]

			chars[node] = ch

			mask := 1 << (ch - 'a')

			update(
				1,
				0,
				n-1,
				pos[node],
				mask,
			)
		} else {
			u, _ := strconv.Atoi(parts[1])
			v, _ := strconv.Atoi(parts[2])

			mask := pathXor(u, v)

			ans = append(
				ans,
				mask == 0 || (mask&(mask-1)) == 0,
			)
		}
	}

	return ans
}

Go-Specific Notes

The Go solution follows exactly the same HLD and segment tree logic. Characters are stored as a mutable []byte slice because Go strings are immutable. Bitmasks comfortably fit within Go's int type because only 26 bits are required.

Worked Examples

Example 1

Input:

n = 3
edges = [[0,1],[1,2]]
s = "aac"

Tree:

0(a)
 |
1(a)
 |
2(c)

Initial masks:

Node	Char	Mask
0	a	001
1	a	001
2	c	100

Query 0 2

Path:

0 -> 1 -> 2

XOR:

001 ^ 001 ^ 100
= 100

Only one bit set.

Result:

true

Update 1 b

Masks become:

Node	Char	Mask
0	a	001
1	b	010
2	c	100

Query 0 2

001 ^ 010 ^ 100
= 111

Three bits set.

Result:

false

Output:

[true, false]

Example 2

Initial masks:

Node	Char
0	a
1	b
2	c
3	a

Query 1 2

Path:

1 -> 0 -> 2

Mask:

b ^ a ^ c

Three odd counts.

false

Update 0 b

Characters:

bbca

Query 2 3

Path:

2 -> 0 -> 3

Characters:

cba

Three odd counts.

false

Update 3 a

No effective change.

Query 1 3

Characters:

bba

Parity:

a -> odd
b -> even

One odd count.

true

Output:

[false, false, true]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log² n)	HLD preprocessing plus O(log² n) per operation
Space	O(n)	Tree, HLD arrays, and segment tree

The two DFS traversals require O(n) time. Building the segment tree also requires O(n). Each update touches a single segment tree path, costing O(log n). Each path query is decomposed into at most O(log n) chain segments, and each segment query costs O(log n), giving O(log² n) total per query.

Test Cases

sol = Solution()

# Example 1
assert sol.palindromePath(
    3,
    [[0, 1], [1, 2]],
    "aac",
    ["query 0 2", "update 1 b", "query 0 2"]
) == [True, False]

# Example 2
assert sol.palindromePath(
    4,
    [[0, 1], [0, 2], [0, 3]],
    "abca",
    [
        "query 1 2",
        "update 0 b",
        "query 2 3",
        "update 3 a",
        "query 1 3"
    ]
) == [False, False, True]

# Single node tree
assert sol.palindromePath(
    1,
    [],
    "a",
    ["query 0 0"]
) == [True]

# Single node update
assert sol.palindromePath(
    1,
    [],
    "a",
    ["update 0 z", "query 0 0"]
) == [True]

# Two-node tree, equal characters
assert sol.palindromePath(
    2,
    [[0, 1]],
    "aa",
    ["query 0 1"]
) == [True]

# Two-node tree, different characters
assert sol.palindromePath(
    2,
    [[0, 1]],
    "ab",
    ["query 0 1"]
) == [False]

# Long chain with updates
assert sol.palindromePath(
    5,
    [[0,1],[1,2],[2,3],[3,4]],
    "abcba",
    [
        "query 0 4",
        "update 2 a",
        "query 0 4"
    ]
) == [True, True]

# Star tree
assert sol.palindromePath(
    5,
    [[0,1],[0,2],[0,3],[0,4]],
    "aaaaa",
    [
        "query 1 2",
        "query 3 4"
    ]
) == [True, True]

# Repeated updates to same node
assert sol.palindromePath(
    3,
    [[0,1],[1,2]],
    "aaa",
    [
        "update 1 b",
        "update 1 a",
        "query 0 2"
    ]
) == [True]

Test Summary

Test	Why
Example 1	Verifies basic query and update behavior
Example 2	Verifies multiple updates and branching paths
Single node tree	Smallest valid input
Single node update	Update correctness on minimum size
Two-node equal characters	Even frequency palindrome
Two-node different characters	Non-palindrome case
Long chain	Worst-case path length structure
Star tree	Many paths sharing root
Repeated updates	Ensures updates overwrite correctly

Edge Cases

Single Node Paths

A query may ask for the path from a node to itself. The path contains exactly one character, and any one-character string can be rearranged into a palindrome. The implementation naturally handles this because the path query returns a mask with exactly one set bit.

Updates That Do Not Change the Character

An update may assign the same character already stored at a node. Incorrect implementations sometimes attempt to apply a delta and accidentally double-count changes. This solution simply replaces the value at the segment tree position with the correct bitmask, so identical updates are harmless.

Highly Unbalanced Trees

A tree may degenerate into a chain of length n. Naive path traversal would become extremely expensive. Heavy-Light Decomposition is specifically designed to handle such cases efficiently, guaranteeing at most O(log n) chain transitions and keeping every operation within O(log² n) time.

LCA Equal to an Endpoint

For a query where one endpoint is an ancestor of the other, the Lowest Common Ancestor is one of the queried nodes. Such cases often cause off-by-one errors in path algorithms. The final HLD step queries the interval [pos[u], pos[v]] after ensuring both nodes are in the same chain, which correctly includes both endpoints exactly once.

Multiple Odd Characters

The palindrome condition depends only on parity. Some implementations incorrectly compute full frequency tables. This solution uses a 26-bit XOR mask, and the condition mask == 0 or (mask & (mask - 1)) == 0 precisely checks whether at most one character has odd frequency.