...

Solution

The key idea is to flatten the tree into an array so that every subtree becomes a contiguous segment.
We run a DFS from the root 1 and record:

• Entry time tin[v] when a vertex v is first visited
• Exit time tout[v] after all its descendants are processed

If t is a global time incremented on entry, we define an order array ord[t] such that
ord[tin[v]] = v.

It is standard that the subtree of v corresponds exactly to the segment
[tin[v], tout[v]] in this DFS order (Euler tour).
Hence, every query “on the subtree of v” reduces to a range operation on [tin[v], tout[v]].

Color Representation as Bitmask

Each vertex color c ∈ {1, …, 60} is represented as a bitmask in a 64-bit integer:

mask(c) = 1 << (c - 1)

For the flattened array A of length n:

A[i] = mask(c_ord[i])

A segment’s set of colors is then the bitwise OR of its elements.
If a segment covers colors S, its mask is:

mask(S) = OR_{x ∈ S} mask(x)

The number of distinct colors is:

#colors = popcount(mask(S))

Segment Tree with Lazy Propagation

We build a segment tree over A with lazy propagation.

For each node x in the tree:

• M_x = bitwise OR of all A[i] for i in this node's segment
• L_x = lazy tag, initially unset (e.g., -1), meaning “no pending assignment.”
  If set, it holds a uniform mask meaning “paint this entire segment with this mask.”

Operations

1) Range Paint (Type 1)

Painting all vertices in the subtree of v with color c means assigning:

V = mask(c)

to the segment [tin[v], tout[v]].

For a fully covered segment:

• Set M_x = V
• Set L_x = V

For partial overlap:

• Push L_x down to children if needed
• Recurse into children

2) Range Query (Type 2)

Counting distinct colors in the subtree of v means:

Ans(v) = popcount(OR_query([tin[v], tout[v]]))

The segment tree merges results by bitwise OR:

res = M_left | M_right

Correctness

We maintain two invariants:

1. If L_x is unset, then M_x is the OR of the actual values in the segment.
2. If L_x is set, then the entire segment is painted with that mask.

Updates replace segments with a constant mask. Push operations ensure children remain consistent.
Because bitwise OR matches set union on these masks, the query result is correct,
and popcount returns the correct count of distinct colors.

Complexity

• Preprocessing (DFS): O(n)
• Range Paint: O(log n)
• Range Query: O(log n)

Total time: O((n + m) log n)
Space: O(n) for the tree and segment tree.

Summary:

1. Flatten the tree via DFS (tin, tout).
2. Store colors as 64-bit masks.
3. Maintain a segment tree with lazy range assignment and range OR queries.
4. Answer queries with popcount of the returned mask.

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

n, m = map(int, input().split())
colors = list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

# Euler Tour Flattening
tin = [0] * (n + 1)
tout = [0] * (n + 1)
order = [0] * (n + 1)
timer = 0

def dfs(u, p):
    global timer
    timer += 1
    tin[u] = timer
    order[timer] = u
    for v in adj[u]:
        if v != p:
            dfs(v, u)
    tout[u] = timer

dfs(1, -1)

size = 1
while size < n:
    size <<= 1

tree = [0] * (2 * size)
lazy = [-1] * (2 * size)

def build():
    for i in range(1, n + 1):
        node = order[i]
        tree[size + i - 1] = 1 << (colors[node - 1] - 1)
    for i in range(size - 1, 0, -1):
        tree[i] = tree[i * 2] | tree[i * 2 + 1]

def apply(node, value):
    tree[node] = value
    lazy[node] = value

def push(node):
    if lazy[node] != -1:
        apply(node * 2, lazy[node])
        apply(node * 2 + 1, lazy[node])
        lazy[node] = -1

def update(l, r, value, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return
    if l <= lx and rx <= r:
        apply(node, value)
        return
    push(node)
    mid = (lx + rx) // 2
    update(l, r, value, node * 2, lx, mid)
    update(l, r, value, node * 2 + 1, mid + 1, rx)
    tree[node] = tree[node * 2] | tree[node * 2 + 1]

def query(l, r, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return 0
    if l <= lx and rx <= r:
        return tree[node]
    push(node)
    mid = (lx + rx) // 2
    return query(l, r, node * 2, lx, mid) | query(l, r, node * 2 + 1, mid + 1, rx)

build()

for _ in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        v, c = q[1], q[2]
        update(tin[v], tout[v], 1 << (c - 1))
    else:
        v = q[1]
        res = query(tin[v], tout[v])
        print(res.bit_count())  # Python 3.10+