TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P6605
  • Problem
  • P6605[COI2019] IZLET
    Limits : Time Limit : - MS   Memory Limit : 524288 KB  SPJ
    Judgment Tips : 6s,512MB
    Description

    信息学竞赛选手眼中的树和普通人眼中的树是不同的,但在这道题中,两种都是正确的。

    p6pou热爱大自然,经常在树林里散步。每当他注视着树林中的树木,都会去欣赏树的大小、节点的度数、若隐若现的规律等等。在舒适的春天里,p6pou更加的被树木所吸引——树木展现出了不同的颜色!

    有一天,p6pou观察到一棵有$N$个节点的树,树上每个节点都有一种颜色。因为某些不可名状的原因,p6pou盯着这棵树看了很长时间,并写下了一个$N\times N$的矩阵。对于树上任意两个节点间的简单路径,p6pou都在矩阵的对应位置记录了路径上不同颜色数量(包括端点)。可惜的是,p6pou专注于欣赏这棵树,只记录下了这个矩阵,没有记录下这个树的形态。

    p6pou需要你的帮助,根据这个矩阵中的数据来确定树的形态和每个节点的颜色,颜色用$1\sim N$的整数表示。p6pou可以向你保证,他记录的矩阵一定是对的,换句话说,一定存在一棵符合条件的树。

    Input Format

    第一行一个整数,表示子任务的编号,数值可能为$1,2,3$。

    第二行一个整数$N(1\leq N\leq 3000)$,表示树的节点数量。节点编号为$1,2,\dots,N$。

    接下来是一个$N$行$N$列的矩阵,第$i$行第$j$列的数表示节点$i$和节点$j$路径上的不同颜色数量。

    Output Format

    第一行输出$N$个空格间隔的整数,依次是每个节点的颜色,颜色应当是$1\sim N$的整数。

    接下来$N-1$行,每行有两个整数$A,B$,表示树的一条边。边、同一条边两个端点都可以按任意的顺序输出。

    Sample Input 1

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

    Sample Output 1

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

    Sample Input 2

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

    Sample Output 2

    1 2 3 2
    1 2
    2 3
    3 4

    Sample Input 3

    1
    5
    1 2 2 2 2
    2 1 1 2 2
    2 1 1 2 2
    2 2 2 1 2
    2 2 2 2 1

    Sample Output 3

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

    Hint

    子任务1(18分)对于20%的数据:矩阵中所有数都是$1$或$2$;
    子任务2(25分)对于28%的数据:当树的形态是$N-1$条边都连接编号相差$1$的两个节点时,存在符合题意的染色方案;
    子任务3(57分)对于52%的数据:没有额外限制。
    (本题有25个测试点,每个测试点4分。除了上述特殊限制外,$n$的大小无梯度)

    本题评测需要花费的时间较长(例如nodgd的程序测了5min才测完),请尽量确保AC再提交(例如先去LOJ上AC了再来NKOJ提交),以减轻评测机工作压力。


    Source  来源COCI,感谢nodgd翻译并提供NKOJ能用的SPJ