F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5100. -- [POI2018]Plan metra

5100: [POI2018]Plan metra

Time Limit: 40 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 478  Solved: 121
[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