Solve jump maximization and palindromic path queries

Part 1: Max Jump Score

Given an integer array nums and an integer k, you start at index 0. From index i, you can jump to any index j such that i < j <= i + k. Each index i has an associated score nums[i]. Your goal is to maximize the sum of scores of the indices visited in a path ending at the last index n-1.

Function Signature

def max_jump_score(nums: List[int], k: int) -> int:

Example

Input: nums = [10, -5, 2, 8, 1], k = 2 Output: 19 Explanation: Path is index 0 -> 2 -> 4. Sum = 10 + 2 + 1 = 13. Wait, path 0 -> 1 -> 2 -> 4 is 10-5+2+1 = 8. Path 0 -> 2 -> 3 -> 4 is 10 + 2 + 8 + 1 = 21. Max is 21.

Part 2: Palindromic Ancestor Paths

Given a tree with n nodes (0 to n-1) where each node has a character c, and a list of queries (u, v), determine if the path from node u to node v can be rearranged to form a palindrome. A path can be rearranged into a palindrome if at most one character appears an odd number of times.

Function Signature

def can_form_palindrome(n: int, edges: List[List[int]], chars: str, queries: List[List[int]]) -> List[bool]:

Constraints

• n <= 10^5
• k 0 -> 2 has characters 'b', 'a', 'a'. Since 'b' appears once and 'a' twice, it can form a palindrome "aba".