#P11755. [COCI 2024/2025 #5] 树树 2 / Stablo II

[COCI 2024/2025 #5] 树树 2 / Stablo II

题目背景

译自 COCI 2024/2025 #5 T5。3.5s,0.5G\texttt{3.5s,0.5G}。满分为 120120

题目描述

给定 nn 个节点的树,初始时所有边边权为 00

qq 次操作,第 ii 次操作将 u,vu,v 最短路径上的边权覆盖ii

最终输出每条边的边权。

输入格式

第一行,正整数 n,qn,q

接下来 (n1)(n-1) 行,每行两个正整数 ui,viu_i,v_i,描述第 ii 条树边 (ui,vi)(u_i,v_i)

接下来 qq 行,每行两个正整数 u,vu,v,描述一次操作。

输出格式

一行 (n1)(n-1) 个非负整数,第 ii 个整数描述第 ii 条树边的边权。

6 2
1 2
2 3
2 4
1 5
4 6
5 2
6 1
2 0 2 1 2
5 4
1 2
2 3
3 4
4 5
5 5
4 3
2 1
2 4
3 4 4 0
5 4
3 5
2 3
4 3
5 1
4 1
5 5
4 2
1 5
1 3 3 4

提示

数据范围

对于 100%100\% 的数据,保证:

  • 2n1062\le n\le 10^6
  • 1q1061\le q\le 10^6
  • 1u,vn1\le u,v\le n
子任务编号 nn\le 特殊性质 得分
1 1 10610^6 A 15 15
2 2 2×1032\times 10^3 B
3 3 10510^5 45 45
4 4 10610^6
  • 特殊性质 A:ui=i,vi=i+1u_i=i,v_i=i+1
  • 特殊性质 B:q103q\le 10^3