Distinct Queries on Tree

You are given a tree T with N nodes (numbered 0 to N-1) and a string S where S[i] is the lowercase letter written on node i.

You must answer Q queries of two types:

Type 1 (Update): 1 U X - Change the letter on node U to the X-th letter of the alphabet (0-indexed, 'a'=0, 'b'=1, ...).

Type 2 (Query): 2 U V - Count the number of distinct letters on the unique simple path from node U to node V.

After processing all queries, you need to calculate a final weighted sum. Let the answers to the Type 2 queries be C1, C2, ..., Ck. The final result is (C1 * 3^1 + C2 * 3^2 + ... + Ck * 3^k).

Return this final sum modulo 1,000,000,007.

Input Format:

The first line contains an integer N.

The second line contains the string S.

The third line contains N-1, the number of edges.

The next N-1 lines each contain two space-separated integers, u and v, representing an edge.

The next line contains an integer Q.

The next Q lines contain queries, each as three space-separated integers (e.g., 1 U X or 2 U V).

Output Format:

Print a single integer representing the final weighted sum of the Type 2 query answers, modulo 1,000,000,007.

Note:

A naive approach would be to find the path for each Type 2 query and count distinct characters, which is too slow O(Q * N).

An efficient O((N+Q) * log^2 N) solution requires advanced data structures. The standard approach is to use Heavy-Light Decomposition to break down any tree path into a logarithmic number of segments. A Segment Tree or Fenwick Tree is then used on the linearized HLD paths. Each node in the segment tree would store a bitmask representing the set of distinct characters in its range, allowing for efficient merging and querying.