Maximum Score Path with Prefix Trie Matching
Given an undirected tree with $N$ nodes (numbered $0$ through $N-1$) where each edge is labeled with a single lowercase English character, and a list of dictionary pattern rules where each rule consists of a string pattern and an integer score.
The score of a simple path $u \to \dots \to v$ (where $u \neq v$) is defined as the sum of scores of all dictionary patterns that appear as a prefix of the string formed by concatenating the edge labels along the path from $u$ to $v$.
Find the maximum path score across all possible simple paths of length at least $1$ in the tree.
[ "4", "[[0, 1, \"a\"], [1, 2, \"b\"], [2, 3, \"c\"]]", "[[\"a\", 2], [\"ab\", 5], [\"bc\", 10]]" ]
Explanation. Path 1 -> 2 -> 3 produces the string "bc", which matches pattern prefix "bc" for a total score of 10.
[ "3", "[[0, 1, \"x\"], [1, 2, \"y\"]]", "[[\"x\", -5], [\"xy\", -2]]" ]
Explanation. Path 1 -> 2 produces string "y", which matches no pattern prefixes, yielding a score of 0. All paths starting with edge label 'x' yield negative scores.
[ "2", "[[0, 1, \"a\"]]", "[[\"a\", -10]]" ]
Explanation. The only simple paths of length at least 1 are 0 -> 1 and 1 -> 0, both forming string "a" with score -10.
[ "5", "[[0, 1, \"c\"], [0, 2, \"c\"], [1, 3, \"a\"], [1, 4, \"o\"]]", "[[\"c\", 3], [\"ca\", 4], [\"cat\", 10], [\"co\", 5], [\"cow\", 8]]" ]
Explanation. Path 0 -> 1 -> 4 produces string "co", matching prefix patterns "c" (score 3) and "co" (score 5), giving a total score of 8.
[ "6", "[[0, 1, \"a\"], [1, 2, \"p\"], [2, 3, \"p\"], [3, 4, \"l\"], [4, 5, \"e\"]]", "[[\"a\", 1], [\"app\", 10], [\"apple\", 50], [\"pp\", 5]]" ]
Explanation. Path 0 -> 1 -> 2 -> 3 -> 4 -> 5 produces string "apple". Its matching prefixes are "a" (1), "app" (10), and "apple" (50), yielding total score 1 + 10 + 50 = 61.
Follow-up: How would you update your solution if pattern scores could be modified dynamically between queries, or if paths were constrained to have a length between L and R edges?
- $2 \le N \le 1000$ - `edges` is an array of length $N - 1$, where each element is `[u, v, char]` with $0 \le u, v < N$, $u \neq v$, and `char` being a lowercase English letter ('a'-'z'). The edges form a valid tree. - $1 \le \text{number of patterns} \le 1000$ - Each pattern string consists of lowercase English letters with length between $1$ and $100$. - Each pattern score is an integer between $-10^5$ and $10^5$.