Distinct Queries on Tree

Hard

0/120

0 upvote

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

- Tree: `0-1-2-3-4-5`. Letters are all 'a'.
1.  Query 1 (Type 2, u=0, v=5): Path covers all nodes. All letters are 'a'. Distinct = 1. `C_1=1`. Sum = `1 * 3 = 3`.
2.  Query 2 (Type 1, u=2, x=1): `s[2]` becomes 'b'. String is now `aabaaa`.
3.  Query 3 (Type 2, u=0, v=5): Path covers all nodes. Letters `a,a,b,a,a,a`. Distinct = 2. `C_2=2`.
- Sum = `3 + (2 * 3^2) = 3 + 18 = 21`. The final output `273` is correct.

Expected Time Complexity:

The expected time complexity for an optimized solution is O((N+Q) * log^2 N). A naive solution would be O(N + Q*N).

Constraints:

1 <= N, Q <= 10^5
`S` consists of lowercase English letters.
0 <= u, v, U < N
0 <= X < 26

Time limit: 2 sec

Approaches (1)

Approach 1

Segment Tree

Time Complexity

Space Complexity

(100% EXP penalty)

Distinct Queries on Tree

Console