P11755 [COCI 2024/2025 #5] 树树 2 / Stablo II
题目背景
译自 [COCI 2024/2025 #5](https://hsin.hr/coci/) T5。$\texttt{3.5s,0.5G}$。满分为 $120$。
题目描述
给定 $n$ 个节点的树，初始时所有边边权为 $0$。
$q$ 次操作，第 $i$ 次操作将 $u,v$ 最短路径上的边权**覆盖**为 $i$。
最终输出每条边的边权。
输入格式
无
输出格式
无
说明/提示
#### 数据范围
对于 $100\%$ 的数据，保证：
- $2\le n\le 10^6$；
- $1\le q\le 10^6$；
- $1\le u,v\le n$。
| 子任务编号 | $n\le$ | 特殊性质 | 得分 |
| :--: | :--: | :--: | :--: |
| $ 1 $ | $10^6$ | A | $ 15 $ |
| $ 2 $ | $2\times 10^3$ | B | $ 15 $ |
| $ 3 $ | $10^5$ | | $ 45 $ |
| $ 4 $ | $10^6$ | | $ 45 $ |
- 特殊性质 A：$u_i=i,v_i=i+1$。
- 特殊性质 B：$q\le 2\times 10^3$。