307070: CF1296F. Berland Beauty
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Berland Beauty
题意翻译
给你一颗大小为 $n$ 的无根树,树边的边权尚未确定 现在你从 $m$ 个人中得知在 $(u,v)$ 这条路径(最短路径)上的最小边权为 $w$ 请你构造一种方案满足这 $m$ 个人的条件,如果不存在,请输出 $-1$题目描述
There are $ n $ railway stations in Berland. They are connected to each other by $ n-1 $ railway sections. The railway network is connected, i.e. can be represented as an undirected tree. You have a map of that network, so for each railway section you know which stations it connects. Each of the $ n-1 $ sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from $ 1 $ to $ 10^6 $ inclusive. You asked $ m $ passengers some questions: the $ j $ -th one told you three values: - his departure station $ a_j $ ; - his arrival station $ b_j $ ; - minimum scenery beauty along the path from $ a_j $ to $ b_j $ (the train is moving along the shortest path from $ a_j $ to $ b_j $ ). You are planning to update the map and set some value $ f_i $ on each railway section — the scenery beauty. The passengers' answers should be consistent with these values. Print any valid set of values $ f_1, f_2, \dots, f_{n-1} $ , which the passengers' answer is consistent with or report that it doesn't exist.输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 2 \le n \le 5000 $ ) — the number of railway stations in Berland. The next $ n-1 $ lines contain descriptions of the railway sections: the $ i $ -th section description is two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n, x_i \ne y_i $ ), where $ x_i $ and $ y_i $ are the indices of the stations which are connected by the $ i $ -th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway. The next line contains a single integer $ m $ ( $ 1 \le m \le 5000 $ ) — the number of passengers which were asked questions. Then $ m $ lines follow, the $ j $ -th line contains three integers $ a_j $ , $ b_j $ and $ g_j $ ( $ 1 \le a_j, b_j \le n $ ; $ a_j \ne b_j $ ; $ 1 \le g_j \le 10^6 $ ) — the departure station, the arrival station and the minimum scenery beauty along his path.
输出格式
If there is no answer then print a single integer -1. Otherwise, print $ n-1 $ integers $ f_1, f_2, \dots, f_{n-1} $ ( $ 1 \le f_i \le 10^6 $ ), where $ f_i $ is some valid scenery beauty along the $ i $ -th railway section. If there are multiple answers, you can print any of them.
输入输出样例
输入样例 #1
4
1 2
3 2
3 4
2
1 2 5
1 3 3
输出样例 #1
5 3 5
输入样例 #2
6
1 2
1 6
3 1
1 5
4 1
4
6 1 3
3 4 1
6 5 2
1 2 5
输出样例 #2
5 3 1 2 1
输入样例 #3
6
1 2
1 6
3 1
1 5
4 1
4
6 1 1
3 4 3
6 5 3
1 2 4
输出样例 #3
-1