F.A.Qs
Home
Discuss
ProblemSet
Status
Ranklist
Contest
入门OJ
Login
Register
捐赠本站
Problem 5100. -- [POI2018]Plan metra
5100: [POI2018]Plan metra
Time Limit:
40 Sec
Memory Limit:
128 MBSec
Special Judge
Submit:
498
Solved:
126
[
Submit
][
Status
][
Discuss
]
Description
有一棵n个点的无根树,每条边有一个正整数权值,表示长度,定义两点距离为在树上的最短路径的长度。
已知2到n-1每个点在树上与1和n的距离,请根据这些信息还原出这棵树。
Input
第一行包含一个正整数n(2<=n<=500000),表示点数。
第二行包含n-2个正整数d(1,2),d(1,3),...,d(1,n-1),分别表示每个点到1的距离。
第三行包含n-2个正整数d(n,2),d(n,3),...,d(n,n-1),分别表示每个点到n的距离。
输入数据保证1<=d<=1000000。
Output
若无解,输出NIE。
否则第一行输出TAK,接下来n-1行每行三个正整数u,v,c(1<=u,v<=n,1<=c<=1000000)
表示存在一条长度为c的连接u和v两点的树边。
若有多组解,输出任意一组。
Sample Input
7
6 6 2 2 1
5 3 5 1 4
Sample Output
TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1
HINT
Source
鸣谢Claris上传试题
[
Submit
][
Status
][
Discuss
]
HOME
Back