Day 050-Q1 — Euler Tour + 遅延SegTree カラーマージ（動的部分木異なる色数クエリ）

問題

$N$ 頂点の根付き木（根は頂点 $1$）が与えられる。各頂点には初期色 $C_i \in [1, K]$ が付いている。次の $Q$ 個のクエリを処理せよ。

• クエリ1: 1 v c — 頂点 $v$ の色を $c$ に変更する。
• クエリ2: 2 v — 頂点 $v$ の部分木に含まれる 異なる色の数 を出力する。

制約

入出力例

7 4 5
1 2 3 1 2 3 4
1 2
1 3
2 4
3 5
3 6
3 7
2 1
1 4 4
2 1
1 2 3
2 3

4
4
3

クエリ 2 3: 頂点3の部分木 = {3,5,6,7}、変更後の色 {3,2,3,4} = {2,3,4} → 3種類

概念図: Euler Tour と distinct count テクニック

ヒント（段階的開示）

from sortedcontainers import SortedList

# 色ごとの Euler Tour 位置管理
color_pos = defaultdict(SortedList)  # color -> sorted positions

# Merge Sort Tree
seg = [SortedList() for _ in range(4 * N)]

# クエリ: [L,R]内でprev_pos[i] < L の個数
def seg_query(node, l, r, ql, qr, threshold):
    if qr < l or r < ql: return 0
    if ql <= l and r <= qr:
        return seg[node].bisect_left(threshold)
    mid = (l + r) // 2
    return (seg_query(2*node, l, mid, ql, qr, threshold) +
            seg_query(2*node+1, mid+1, r, ql, qr, threshold))

模範解答 (Python)

コピーimport sys
from sortedcontainers import SortedList
from collections import defaultdict
input = sys.stdin.readline

def solve():
    N, K, Q = map(int, input().split())
    C_raw = list(map(int, input().split()))
    adj = defaultdict(list)
    for _ in range(N - 1):
        u, v = map(int, input().split())
        adj[u].append(v); adj[v].append(u)

    # Euler Tour (反復DFS)
    tin = [0]*(N+1); tout = [0]*(N+1); order = [0]*N; timer = [0]
    stack = [(1, -1, False)]
    while stack:
        v, par, leaving = stack.pop()
        if leaving:
            tout[v] = timer[0]-1; continue
        tin[v] = timer[0]; order[timer[0]] = v; timer[0] += 1
        stack.append((v, par, True))
        for u in adj[v]:
            if u != par: stack.append((u, v, False))

    color_at = [C_raw[order[i]-1] for i in range(N)]
    color_pos = defaultdict(SortedList)
    for i in range(N): color_pos[color_at[i]].add(i)

    prev_pos = [-1]*N
    for i in range(N):
        sl = color_pos[color_at[i]]; idx = sl.index(i)
        if idx > 0: prev_pos[i] = sl[idx-1]

    # Merge Sort Tree
    seg = [SortedList() for _ in range(4*N)]
    def build(node, l, r):
        for i in range(l, r+1): seg[node].add(prev_pos[i])
        if l == r: return
        mid=(l+r)//2; build(2*node,l,mid); build(2*node+1,mid+1,r)
    def seg_upd(node, l, r, pos, ov, nv):
        seg[node].remove(ov); seg[node].add(nv)
        if l==r: return
        mid=(l+r)//2
        if pos<=mid: seg_upd(2*node,l,mid,pos,ov,nv)
        else: seg_upd(2*node+1,mid+1,r,pos,ov,nv)
    def seg_qry(node, l, r, ql, qr, th):
        if qr0 else -1
            prev_pos[pos]=new_pp; seg_upd(1,0,N-1,pos,old_pp,new_pp)
            if idx2+1