Tap here to switch tabs
Problem
Submissions

Problem: Count Paths That Can Form a Palindrome in a Tree

Try to solve the Count Paths That Can Form a Palindrome in a Tree problem.

Statement

You are given a tree consisting of n nodes numbered from 00 to n −1- 1, rooted at node 00. The structure of the tree is defined by a 00 indexed integer array parent of size n, where parent[i] denotes the parent of node i, and parent[00] == −1-1.

You are also provided with a string s of length n, where each character s[i] represents the character assigned to the directed edge connecting parent[i] to node i for every i ≥1\geq 1. The value of s[00] is not used.

A path between two distinct nodes can form a palindrome if the sequence of characters on the unique path between them can be rearranged into a palindrome.

Return the total number of pairs (u, v) such that 0≤0 \leq u << v << n, and the characters along the path between node u and node v can form a palindrome.

Constraints:

  • n == parent.length == s.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq parent[i] ≤\leq n −1- 1 for all i ≥1\geq 1

  • parent[00] == −1-1

  • parent represents a valid tree.

  • s consists of only lowercase English letters.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Paths That Can Form a Palindrome in a Tree

Try to solve the Count Paths That Can Form a Palindrome in a Tree problem.

Statement

You are given a tree consisting of n nodes numbered from 00 to n −1- 1, rooted at node 00. The structure of the tree is defined by a 00 indexed integer array parent of size n, where parent[i] denotes the parent of node i, and parent[00] == −1-1.

You are also provided with a string s of length n, where each character s[i] represents the character assigned to the directed edge connecting parent[i] to node i for every i ≥1\geq 1. The value of s[00] is not used.

A path between two distinct nodes can form a palindrome if the sequence of characters on the unique path between them can be rearranged into a palindrome.

Return the total number of pairs (u, v) such that 0≤0 \leq u << v << n, and the characters along the path between node u and node v can form a palindrome.

Constraints:

  • n == parent.length == s.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq parent[i] ≤\leq n −1- 1 for all i ≥1\geq 1

  • parent[00] == −1-1

  • parent represents a valid tree.

  • s consists of only lowercase English letters.