Solve jump maximization and palindromic path queries

You are given two independent algorithmic problems.

Problem 1 — Jump game with special destinations (maximize score)

You are given an integer array arr of length n (0-indexed). You start at index 0 and must end exactly at index n-1.

• Your score is the sum of arr[i] over all visited indices (including start and end).
• From an index i , you may jump to:
  1. i + 1 (if i + 1 < n ), or
  2. any index j such that j > i and j is a positive integer whose ones digit is 3 (i.e., j ∈ {3, 13, 23, 33, ...} ) and j < n .

It is guaranteed that n-1 is reachable.

Task: Return the maximum possible score achievable.

Input: int[] arr

Output: long (or int if you can prove no overflow)

Problem 2 — Count ancestor endpoints forming a palindrome (tree queries)

You are given a rooted tree with root node 0.

• treeNodes : number of nodes N (nodes are 0..N-1 )
• nodes : char[] of length N , where nodes[i] is the lowercase letter ( 'a'..'z' ) stored on node i
• nodeFrom , nodeTo : integer arrays of length N-1 describing directed edges nodeFrom[k] -> nodeTo[k] (parent to child). This forms a valid tree.
• queries : integer array of query nodes.

For each query node u = queries[t], consider the unique path from u up to the root 0.

For every endpoint v on this path (where v is an ancestor of u, including u itself), form the multiset/string of characters on the nodes along the path from u to v (inclusive). The characters may be rearranged arbitrarily.

A path u -> ... -> v is counted if its characters can be rearranged into a palindrome (equivalently: at most one character has an odd frequency).

Task: For each query node u, return the number of ancestors v (including u) such that the path from u to v can be rearranged into a palindrome.

Output: int[] res where res[t] answers queries[t].

Example

N = 4
nodes = [ 'z', 'a', 'a', 'a' ]
nodeFrom = [0, 0, 1]
nodeTo   = [1, 2, 3]
queries = [3]

Tree edges: 0->1, 0->2, 1->3. Query u=3 has path to root: 3(a) -> 1(a) -> 0(z). Valid endpoints:

• v=3 : "a" (palindrome)
• v=1 : "aa" (palindrome)
• v=0 : "aaz" can be rearranged to "aza" (palindrome) So the output is [3] .

Constraints (assume typical OA scale)

You should design an algorithm that is efficient for large n/N/|queries| (e.g., up to 10^5 or more).