3841. Palindromic Path Queries in a Tree

Description

You are given an undirected tree with n nodes labeled 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [u_i, v_i] indicates an undirected edge between nodes u_i and v_i.

You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i.

You are also given a string array queries, where each queries[i] is either:

"update u_i c": Change the character at node u_i to c. Formally, update s[u_i] = c.
"query u_i v_i": Determine whether the string formed by the characters on the unique path from u_i to v_i (inclusive) can be rearranged into a palindrome.

Return a boolean array answer, where answer[j] is true if the j^th query of type "query u_i v_i" can be rearranged into a palindrome, and false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]

Output: [true,false]

Explanation:

"query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true.
"update 1 b": Update node 1 to 'b', now s = "abc".
"query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.

Thus, answer = [true, false].

Example 2:

Input: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]

Output: [false,false,true]

Explanation:

"query 1 2": Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false.
"update 0 b": Update node 0 to 'b', now s = "bbca".
"query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
"update 3 a": Update node 3 to 'a', s = "bbca".
"query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.

Thus, answer = [false, false, true].

Constraints:

1 <= n == s.length <= 5 * 10⁴
edges.length == n - 1
edges[i] = [u_i, v_i]
0 <= u_i, v_i <= n - 1
s consists of lowercase English letters.
The input is generated such that edges represents a valid tree.
1 <= queries.length <= 5 * 10⁴
- queries[i] = "update u_i c" or
- queries[i] = "query u_i v_i"
- 0 <= u_i, v_i <= n - 1
- c is a lowercase English letter.

Solutions

Solution 1

class BinaryIndexedTree {
    int n;
    int[] tree;

    BinaryIndexedTree(int n) {
        this.n = n;
        tree = new int[n + 1];
    }

    void update(int i, int delta) {
        for (i++; i <= n; i += i & -i) {
            tree[i] ^= delta;
        }
    }

    int query(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res ^= tree[i];
        }
        return res;
    }
}

class Solution {
    List<Integer>[] g;
    int[] parent, depth, tin, tout, bit;
    int[][] up;
    int timer, m;

    public List<Boolean> palindromePath(int n, int[][] edges, String s, String[] queries) {
        g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }

        parent = new int[n];
        depth = new int[n];
        tin = new int[n];
        tout = new int[n];
        timer = 0;
        dfs(0, -1);

        m = 32 - Integer.numberOfLeadingZeros(n);
        up = new int[m][n];
        System.arraycopy(parent, 0, up[0], 0, n);
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }

        bit = new int[n];
        for (int i = 0; i < n; i++) {
            bit[i] = 1 << (s.charAt(i) - 'a');
        }

        BinaryIndexedTree tree = new BinaryIndexedTree(n);
        for (int i = 0; i < n; i++) {
            tree.update(tin[i], bit[i]);
            tree.update(tout[i], bit[i]);
        }

        List<Boolean> ans = new ArrayList<>();
        for (String q : queries) {
            String[] parts = q.split(" ");
            int u = Integer.parseInt(parts[1]);
            if (parts[0].equals("update")) {
                int x = bit[u];
                int y = 1 << (parts[2].charAt(0) - 'a');
                if (x != y) {
                    int delta = x ^ y;
                    tree.update(tin[u], delta);
                    tree.update(tout[u], delta);
                    bit[u] = y;
                }
            } else {
                int v = Integer.parseInt(parts[2]);
                int w = lca(u, v);
                int mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
                ans.add((mask & (mask - 1)) == 0);
            }
        }
        return ans;
    }

    void dfs(int u, int p) {
        parent[u] = p == -1 ? 0 : p;
        tin[u] = timer++;
        for (int v : g[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
        tout[u] = timer;
    }

    int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            int t = u;
            u = v;
            v = t;
        }
        int d = depth[u] - depth[v];
        for (int j = 0; d > 0; j++, d >>= 1) {
            if ((d & 1) != 0) {
                u = up[j][u];
            }
        }
        if (u == v) {
            return u;
        }
        for (int j = m - 1; j >= 0; j--) {
            if (up[j][u] != up[j][v]) {
                u = up[j][u];
                v = up[j][v];
            }
        }
        return parent[u];
    }
}

class BinaryIndexedTree {
    int n;
    vector<int> tree;

public:
    BinaryIndexedTree(int n)
        : n(n)
        , tree(n + 1) {}

    void update(int i, int delta) {
        for (++i; i <= n; i += i & -i) {
            tree[i] ^= delta;
        }
    }

    int query(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res ^= tree[i];
        }
        return res;
    }
};

class Solution {
    vector<vector<int>> g, up;
    vector<int> parent, depth, tin, tout, bit;
    int timer, m;

    void dfs(int u, int p) {
        parent[u] = p == -1 ? 0 : p;
        tin[u] = timer++;
        for (int v : g[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
        tout[u] = timer;
    }

    int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        int d = depth[u] - depth[v];
        for (int j = 0; d; j++, d >>= 1) {
            if (d & 1) {
                u = up[j][u];
            }
        }
        if (u == v) {
            return u;
        }
        for (int j = m - 1; j >= 0; j--) {
            if (up[j][u] != up[j][v]) {
                u = up[j][u];
                v = up[j][v];
            }
        }
        return parent[u];
    }

public:
    vector<bool> palindromePath(int n, vector<vector<int>>& edges, string s, vector<string>& queries) {
        g.assign(n, {});
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }

        parent.resize(n);
        depth.assign(n, 0);
        tin.resize(n);
        tout.resize(n);
        timer = 0;
        dfs(0, -1);

        m = 32 - __builtin_clz(n);
        up.assign(m, vector<int>(n));
        up[0] = parent;
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }

        bit.resize(n);
        for (int i = 0; i < n; i++) {
            bit[i] = 1 << (s[i] - 'a');
        }

        BinaryIndexedTree tree(n);
        for (int i = 0; i < n; i++) {
            tree.update(tin[i], bit[i]);
            tree.update(tout[i], bit[i]);
        }

        vector<bool> ans;
        for (string& q : queries) {
            stringstream ss(q);
            string op;
            int u;
            ss >> op >> u;
            if (op == "update") {
                string c;
                ss >> c;
                int y = 1 << (c[0] - 'a');
                if (bit[u] != y) {
                    int delta = bit[u] ^ y;
                    tree.update(tin[u], delta);
                    tree.update(tout[u], delta);
                    bit[u] = y;
                }
            } else {
                int v;
                ss >> v;
                int w = lca(u, v);
                int mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
                ans.push_back((mask & (mask - 1)) == 0);
            }
        }
        return ans;
    }
};

class BinaryIndexedTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        i += 1
        while i <= self.n:
            self.tree[i] ^= delta
            i += i & -i

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


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

        parent = [-1] * n
        depth = [0] * n
        tin = [0] * n
        tout = [0] * n
        timer = 0

        def dfs(u: int, p: int) -> None:
            nonlocal timer
            parent[u] = p
            tin[u] = timer
            timer += 1
            for v in g[u]:
                if v != p:
                    depth[v] = depth[u] + 1
                    dfs(v, u)
            tout[u] = timer

        dfs(0, -1)

        m = n.bit_length()
        up = [parent[:]]
        up[0][0] = 0
        for j in range(1, m):
            prev = up[-1]
            up.append([prev[prev[i]] for i in range(n)])

        def lca(u: int, v: int) -> int:
            if depth[u] < depth[v]:
                u, v = v, u
            d = depth[u] - depth[v]
            j = 0
            while d:
                if d & 1:
                    u = up[j][u]
                d >>= 1
                j += 1
            if u == v:
                return u
            for j in range(m - 1, -1, -1):
                if up[j][u] != up[j][v]:
                    u = up[j][u]
                    v = up[j][v]
            return parent[u]

        bit = [1 << (ord(c) - ord("a")) for c in s]
        tree = BinaryIndexedTree(n)

        for u in range(n):
            tree.update(tin[u], bit[u])
            tree.update(tout[u], bit[u])

        ans = []
        for q in queries:
            op, a, b = q.split()
            u = int(a)
            if op == "update":
                x = bit[u]
                y = 1 << (ord(b) - ord("a"))
                if x != y:
                    delta = x ^ y
                    tree.update(tin[u], delta)
                    tree.update(tout[u], delta)
                    bit[u] = y
            else:
                v = int(b)
                w = lca(u, v)
                mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w]
                ans.append(mask & (mask - 1) == 0)

        return ans

type BinaryIndexedTree struct {
	n    int
	tree []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{n: n, tree: make([]int, n+1)}
}

func (b *BinaryIndexedTree) update(i, delta int) {
	for i++; i <= b.n; i += i & -i {
		b.tree[i] ^= delta
	}
}

func (b *BinaryIndexedTree) query(i int) int {
	res := 0
	for ; i > 0; i -= i & -i {
		res ^= b.tree[i]
	}
	return res
}

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

	parent := make([]int, n)
	depth := make([]int, n)
	tin := make([]int, n)
	tout := make([]int, n)
	timer := 0

	var dfs func(int, int)
	dfs = func(u, p int) {
		if p == -1 {
			parent[u] = 0
		} else {
			parent[u] = p
		}
		tin[u] = timer
		timer++
		for _, v := range g[u] {
			if v != p {
				depth[v] = depth[u] + 1
				dfs(v, u)
			}
		}
		tout[u] = timer
	}
	dfs(0, -1)

	m := 1
	for (1 << m) <= n {
		m++
	}
	up := make([][]int, m)
	up[0] = append([]int(nil), parent...)
	for j := 1; j < m; j++ {
		up[j] = make([]int, n)
		for i := 0; i < n; i++ {
			up[j][i] = up[j-1][up[j-1][i]]
		}
	}

	bit := make([]int, n)
	for i := 0; i < n; i++ {
		bit[i] = 1 << (s[i] - 'a')
	}

	tree := NewBinaryIndexedTree(n)
	for i := 0; i < n; i++ {
		tree.update(tin[i], bit[i])
		tree.update(tout[i], bit[i])
	}

	lca := func(u, v int) int {
		if depth[u] < depth[v] {
			u, v = v, u
		}
		d := depth[u] - depth[v]
		for j := 0; d > 0; j++ {
			if d&1 != 0 {
				u = up[j][u]
			}
			d >>= 1
		}
		if u == v {
			return u
		}
		for j := m - 1; j >= 0; j-- {
			if up[j][u] != up[j][v] {
				u = up[j][u]
				v = up[j][v]
			}
		}
		return parent[u]
	}

	ans := make([]bool, 0)
	for _, q := range queries {
		var op string
		var u int
		fmt.Sscanf(q, "%s %d", &op, &u)
		if op == "update" {
			var c string
			fmt.Sscanf(q, "%s %d %s", &op, &u, &c)
			y := 1 << (c[0] - 'a')
			if bit[u] != y {
				delta := bit[u] ^ y
				tree.update(tin[u], delta)
				tree.update(tout[u], delta)
				bit[u] = y
			}
		} else {
			var v int
			fmt.Sscanf(q, "%s %d %d", &op, &u, &v)
			w := lca(u, v)
			mask := tree.query(tin[u]+1) ^ tree.query(tin[v]+1) ^ bit[w]
			ans = append(ans, mask&(mask-1) == 0)
		}
	}
	return ans
}

class BinaryIndexedTree {
    n: number;
    tree: number[];

    constructor(n: number) {
        this.n = n;
        this.tree = Array(n + 1).fill(0);
    }

    update(i: number, delta: number): void {
        for (i++; i <= this.n; i += i & -i) {
            this.tree[i] ^= delta;
        }
    }

    query(i: number): number {
        let res = 0;
        for (; i > 0; i -= i & -i) {
            res ^= this.tree[i];
        }
        return res;
    }
}

function palindromePath(n: number, edges: number[][], s: string, queries: string[]): boolean[] {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
        g[v].push(u);
    }

    const parent = Array(n).fill(0);
    const depth = Array(n).fill(0);
    const tin = Array(n).fill(0);
    const tout = Array(n).fill(0);
    let timer = 0;

    function dfs(u: number, p: number): void {
        parent[u] = p === -1 ? 0 : p;
        tin[u] = timer++;
        for (const v of g[u]) {
            if (v !== p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
        tout[u] = timer;
    }
    dfs(0, -1);

    const m = 32 - Math.clz32(n);
    const up: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
    up[0] = [...parent];
    for (let j = 1; j < m; j++) {
        for (let i = 0; i < n; i++) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }

    const bit = Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        bit[i] = 1 << (s.charCodeAt(i) - 97);
    }

    const tree = new BinaryIndexedTree(n);
    for (let i = 0; i < n; i++) {
        tree.update(tin[i], bit[i]);
        tree.update(tout[i], bit[i]);
    }

    function lca(u: number, v: number): number {
        if (depth[u] < depth[v]) {
            [u, v] = [v, u];
        }
        let d = depth[u] - depth[v];
        for (let j = 0; d > 0; j++, d >>= 1) {
            if (d & 1) {
                u = up[j][u];
            }
        }
        if (u === v) {
            return u;
        }
        for (let j = m - 1; j >= 0; j--) {
            if (up[j][u] !== up[j][v]) {
                u = up[j][u];
                v = up[j][v];
            }
        }
        return parent[u];
    }

    const ans: boolean[] = [];
    for (const q of queries) {
        const parts = q.split(' ');
        const u = Number(parts[1]);
        if (parts[0] === 'update') {
            const y = 1 << (parts[2].charCodeAt(0) - 97);
            if (bit[u] !== y) {
                const delta = bit[u] ^ y;
                tree.update(tin[u], delta);
                tree.update(tout[u], delta);
                bit[u] = y;
            }
        } else {
            const v = Number(parts[2]);
            const w = lca(u, v);
            const mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
            ans.push((mask & (mask - 1)) === 0);
        }
    }
    return ans;
}

struct BinaryIndexedTree {
    n: usize,
    tree: Vec<i32>,
}

impl BinaryIndexedTree {
    fn new(n: usize) -> Self {
        Self {
            n,
            tree: vec![0; n + 1],
        }
    }

    fn update(&mut self, mut i: usize, delta: i32) {
        i += 1;
        while i <= self.n {
            self.tree[i] ^= delta;
            i += i & i.wrapping_neg();
        }
    }

    fn query(&self, mut i: usize) -> i32 {
        let mut res = 0;
        while i > 0 {
            res ^= self.tree[i];
            i -= i & i.wrapping_neg();
        }
        res
    }
}

impl Solution {
    pub fn palindrome_path(
        n: i32,
        edges: Vec<Vec<i32>>,
        s: String,
        queries: Vec<String>,
    ) -> Vec<bool> {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            let u = e[0] as usize;
            let v = e[1] as usize;
            g[u].push(v);
            g[v].push(u);
        }

        let mut parent = vec![0usize; n];
        let mut depth = vec![0usize; n];
        let mut tin = vec![0usize; n];
        let mut tout = vec![0usize; n];
        let mut timer = 0usize;

        fn dfs(
            u: usize,
            p: usize,
            g: &[Vec<usize>],
            parent: &mut [usize],
            depth: &mut [usize],
            tin: &mut [usize],
            tout: &mut [usize],
            timer: &mut usize,
        ) {
            parent[u] = if p == usize::MAX { 0 } else { p };
            tin[u] = *timer;
            *timer += 1;
            for &v in &g[u] {
                if v != p {
                    depth[v] = depth[u] + 1;
                    dfs(v, u, g, parent, depth, tin, tout, timer);
                }
            }
            tout[u] = *timer;
        }
        dfs(
            0,
            usize::MAX,
            &g,
            &mut parent,
            &mut depth,
            &mut tin,
            &mut tout,
            &mut timer,
        );

        let m = (32 - (n as u32).leading_zeros()) as usize;
        let mut up = vec![vec![0usize; n]; m];
        up[0].clone_from(&parent);
        for j in 1..m {
            for i in 0..n {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }

        let lca = |mut u: usize, mut v: usize| -> usize {
            if depth[u] < depth[v] {
                std::mem::swap(&mut u, &mut v);
            }
            let mut d = depth[u] - depth[v];
            let mut j = 0;
            while d > 0 {
                if d & 1 == 1 {
                    u = up[j][u];
                }
                d >>= 1;
                j += 1;
            }
            if u == v {
                return u;
            }
            for j in (0..m).rev() {
                if up[j][u] != up[j][v] {
                    u = up[j][u];
                    v = up[j][v];
                }
            }
            parent[u]
        };

        let bytes = s.as_bytes();
        let mut bit = vec![0i32; n];
        for i in 0..n {
            bit[i] = 1 << (bytes[i] - b'a') as u32;
        }

        let mut tree = BinaryIndexedTree::new(n);
        for i in 0..n {
            tree.update(tin[i], bit[i]);
            tree.update(tout[i], bit[i]);
        }

        let mut ans = Vec::new();
        for q in &queries {
            let parts: Vec<&str> = q.split(' ').collect();
            let u: usize = parts[1].parse().unwrap();
            if parts[0] == "update" {
                let x = bit[u];
                let y = 1 << (parts[2].as_bytes()[0] - b'a') as u32;
                if x != y {
                    let delta = x ^ y;
                    tree.update(tin[u], delta);
                    tree.update(tout[u], delta);
                    bit[u] = y;
                }
            } else {
                let v: usize = parts[2].parse().unwrap();
                let w = lca(u, v);
                let mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
                ans.push(mask & (mask - 1) == 0);
            }
        }
        ans
    }
}

3841 - Palindromic Path Queries in a Tree

3841. Palindromic Path Queries in a Tree

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3841. Palindromic Path Queries in a Tree

Description

Solutions

Solution 1

All Problems

All Solutions