#1867. 熟练
熟练
熟练
题目描述
标题: 熟练 - Problem - QOJ.ac
#9607. 熟练
The problem was used in the following contests:
给定大小为 n 的树和 m 条树上的简单路径。你需要给每条路径分配一个颜色 ci,使得任意两条颜色相同的路径,不经过相同的点。
求最少需要几种颜色,并构造方案。
输入格式
本题有多组测试数据。
输入的第一行包含一个整数 c,表示子任务编号。c=0 表示该测试点为样例。
输入的第二行包含一个整数 t,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据:
输入的第一行包含两个正整数 n,m。
接下来 n−1 行,第 i 行包含两个正整数 ui,vi,表示树的第 i 条边为 (ui,vi)。
接下来 m 行,第 i 行包含两个正整数 ai,bi,表示第 i 条路径为 ai 到 bi 的简单路径。
输出格式
对于每组测试数据:
第一行包含一个正整数 k,表示最少需要几种颜色。
第二行包含 m 个正整数,第 i 个数为第 i 条链的颜色 ci,你需要保证 1≤ci≤k。
如果你输出的 k 正确,ci 序列符合格式但不符合题目要求,可以获得该测试点 15% 的分数。
样例
输入
0
3
3 3
1 2
2 3
3 2
2 1
2 3
7 4
1 2
1 3
2 4
2 5
5 6
6 7
6 3
3 6
5 2
5 6
10 3
1 2
1 3
1 4
3 5
3 6
5 7
5 8
7 9
1 10
8 3
1 2
6 8
输出
3
1 2 3
4
1 2 3 4
2
1 1 2
数据范围
对于所有数据,1≤t≤105,1≤n,m,∑n,∑m≤5×105,1≤ui,vi,ai,bi≤n。
- subtask1 (3 pts):n,m≤5。
- subtask2 (14 pts):m≤5。
- subtask3 (9 pts):∀1≤i<n,ui=i,vi=i+1。
- subtask4 (20 pts):n,m≤1000,∑n,∑m≤5000。
- subtask5 (22 pts):∑n,∑m≤105。
- subtask6 (32 pts):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
0
3
3 3
1 2
2 3
3 2
2 1
2 3
7 4
1 2
1 3
2 4
2 5
5 6
6 7
6 3
3 6
5 2
5 6
10 3
1 2
1 3
1 4
3 5
3 6
5 7
5 8
7 9
1 10
8 3
1 2
6 8
3
1 2 3
4
1 2 3 4
2
1 1 2