提出 #18047488

---

ソースコード 拡げる

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n = int(readline())
n,Q = map(int,readline().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a-1].append((b-1,i))
    g[b-1].append((a-1,i))

eid = [-1]*n 
order = []
st = [0]
parent = [-1]*n
while st:
    v = st.pop()
    order.append(v)
    for c,i in g[v]:
        if c != parent[v]:
            st.append(c)
            eid[c] = i
            parent[c] = v

q = [[] for _ in range(n)]
for t in range(Q):
    u,v,c = map(int,readline().split())
    q[u-1].append((t,c))
    q[v-1].append((t,c))

from heapq import *
col = [0]*(n-1)
dp = [[] for _ in range(n)]
for i in order[n-1:0:-1]:
    for t,c in q[i]:
        heappush(dp[i],(-t,c))
    while dp[i]:
        a = heappop(dp[i])
        if dp[i] and dp[i][0][0] == a[0]:
            heappop(dp[i])
        else:
            heappush(dp[i],a)
            break
    if dp[i]:
        col[eid[i]] = dp[i][0][1]
    
    p = parent[i]
    if len(dp[i]) > len(dp[p]):
        dp[i],dp[p] = dp[p],dp[i]
    for a in dp[i]:
        heappush(dp[p],a)

print(*col,sep="\n")

提出情報

ジャッジ結果