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

题目背景

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

题目描述

给定 $n$ 个节点的树，初始时所有边边权为 $0$。

$q$ 次操作，第 $i$ 次操作将 $u,v$ 最短路径上的边权覆盖为 $i$。

最终输出每条边的边权。

输入格式

第一行，正整数 $n,q$。

接下来 $(n-1)$ 行，每行两个正整数 $u_i,v_i$，描述第 $i$ 条树边 $(u_i,v_i)$。

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

输出格式

一行 $(n-1)$ 个非负整数，第 $i$ 个整数描述第 $i$ 条树边的边权。

输入输出样例 #1

输入 #1

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

输出 #1

2 0 2 1 2

输入输出样例 #2

输入 #2

5 4
1 2
2 3
3 4
4 5
5 5
4 3
2 1
2 4

输出 #2

3 4 4 0

输入输出样例 #3

输入 #3

5 4
3 5
2 3
4 3
5 1
4 1
5 5
4 2
1 5

输出 #3

1 3 3 4

说明/提示

数据范围

对于 $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
$3$	$10^5$		$45$
$4$	$10^6$

• 特殊性质 A：$u_i=i,v_i=i+1$。
• 特殊性质 B：$q\le 2\times 10^3$。

#5727. 「COCI 2024/2025 #5」Stablo II

标签: 传统 | 时间限制: 3500 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #5 T5「Stablo II」

Patrik 收到了一棵包含 $n$ 个节点的树。他决定使用 $k$ 种不同的颜色为这棵树的边染色。

起初，树上的所有边都被涂上了颜色 $0$。他将按顺序使用从第 $1$ 种到第 $k$ 种颜色，其中在涂第 $i$ 种颜色时，他会将从第 $x_{i}$ 个节点到第 $y_{i}$ 个节点的最短路径上的所有边都涂上该颜色。若路径上的某条边已经被涂过色，新颜色将覆盖旧颜色。

请帮 Patrik 确定每条边最终的颜色。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 10^{6}, 1 \leq k \leq 10^{6})$，分别代表树的节点数量和颜色的种类数。

接下来的 $n-1$ 行中，每行包含两个整数 $u_{i}$ 和 $v_{i}$ $(1 \leq u_{i}, v_{i} \leq n)$，代表第 $i$ 条边连接节点 $u_{i}$ 和 $v_{i}$。保证这些边构成一棵树。

接下来的 $k$ 行中，每行包含两个整数 $x_{i}$ 和 $y_{i}$ $(1 \leq x_{i}, y_{i} \leq n)$，代表 Patrik 在这两个节点之间的路径上进行染色。

输出格式

在一行中，按输入中给出的边的顺序，依次输出每条边最终的颜色。

样例 1

输入

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

输出

2 0 2 1 2

使用第一种颜色时，他涂了第 $1$ 条和第 $4$ 条边；接着使用第二种颜色时，他涂了第 $1$ 条、第 $3$ 条和第 $5$ 条边。

样例 2

输入

5 4
1 2
2 3
3 4
4 5
5 5
4 3
2 1
2 4

输出

3 4 4 0

样例 3

输入

5 4
3 5
2 3
4 3
5 1
4 1
5 5
4 2
1 5

输出

1 3 3 4

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$15$	对于每个 $i$，满足 $u_{i}=i, v_{i}=i+1$
$2$	$15$	$n, k \leq 2000$
$3$	$45$	$n \leq 10^{5}$
$4$	$45$	无附加限制