309953: CF1764F. Doremy's Experimental Tree
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doremy's Experimental Tree
题意翻译
Doremy 有一颗树，边有权值。 她在这棵树上做了 $\frac{n(n+1)}{2}$ 次实验。 每次实验中她会先添加一条边 $(i,j)$（$j \leq i$），其边权为 $1$。这会使树变成一棵基环树。 她会求出每个点到环上距其最近的点的距离，并将 $n$ 个得到的距离求和，记为 $f(i,j)$。 形式化的，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有： $$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$ Doremy 对于所有的 $1 \leq j \leq i \leq n$ 写下了所有 $f(i,j)$，但是在睡了一觉后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。 保证有解。题目描述
Doremy has an edge-weighted tree with $ n $ vertices whose weights are integers between $ 1 $ and $ 10^9 $ . She does $ \frac{n(n+1)}{2} $ experiments on it. In each experiment, Doremy chooses vertices $ i $ and $ j $ such that $ j \leq i $ and connects them directly with an edge with weight $ 1 $ . Then, there is exactly one cycle (or self-loop when $ i=j $ ) in the graph. Doremy defines $ f(i,j) $ as the sum of lengths of shortest paths from every vertex to the cycle. Formally, let $ \mathrm{dis}_{i,j}(x,y) $ be the length of the shortest path between vertex $ x $ and $ y $ when the edge $ (i,j) $ of weight $ 1 $ is added, and $ S_{i,j} $ be the set of vertices that are on the cycle when edge $ (i,j) $ is added. Then, $$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$ Doremy writes down all values of $ f(i,j) $ such that $ 1 \leq j \leq i \leq n $ , then goes to sleep. However, after waking up, she finds that the tree has gone missing. Fortunately, the values of $ f(i,j) $ are still in her notebook, and she knows which $ i $ and $ j $ they belong to. Given the values of $ f(i,j)$, can you help her restore the tree? It is guaranteed that at least one suitable tree exists.输入输出格式
输入格式
The first line of input contains a single integer $ n $ ($ 2 \le n \le 2000 $) — the number of vertices in the tree. The following $ n $ lines contain a lower-triangular matrix with $ i $ integers on the $ i $ -th line; the $ j $ -th integer on the $ i $ -th line is $ f(i,j) $ ( $ 0 \le f(i,j) \le 2\cdot 10^{15} $ ). It is guaranteed that there exists a tree whose weights are integers between $ 1 $ and $ 10^9 $ such that the values of $ f(i,j) $ of the tree match those given in the input.
输出格式
Print $ n-1 $ lines describing the tree. In the $ i $ -th line of the output, output three integers $ u_i $ , $ v_i $ , $ w_i $ ( $ 1 \le u_i,v_i \le n $ , $ 1 \le w_i \le 10^9 $ ), representing an edge $ (u_i,v_i) $ whose weight is $ w_i $ . If there are multiple answers, you may output any. All edges must form a tree and all values of $ f(i,j) $ must match those given in the input.
输入输出样例
输入样例 #1
3
7
3 5
0 2 8输出样例 #1
2 3 3
1 2 2输入样例 #2
9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748217280 1748217069 5741194692 749972427 10439821163
2377558289 2377559274 2377559063 6370536686 1379314421 5028071980 8866466178
1746983932 1746984917 1746984706 5739962329 748740064 10438588800 5026839617 10448447704
2341942133 2341943118 2341942907 6334920530 1343698265 4992455824 8830850022 4991223461 9115779270输出样例 #2
1 2 985
2 3 211
2 4 998244353
2 5 998244853
4 6 671232353
6 8 1232363
4 7 356561356
7 9 35616156说明
In the first test case, the picture below, from left to right, from top to bottom, shows the graph when pairs $ (1,1) $ , $ (1,2) $ , $ (1,3) $ , $ (2,2) $ , $ (2,3) $ , $ (3,3) $ are connected with an edge, respectively. The nodes colored yellow are on the cycle. Input
题意翻译
Doremy 有一颗树，边有权值。 她在这棵树上做了 $\frac{n(n+1)}{2}$ 次实验。 每次实验中她会先添加一条边 $(i,j)$（$j \leq i$），其边权为 $1$。这会使树变成一棵基环树。 她会求出每个点到环上距其最近的点的距离，并将 $n$ 个得到的距离求和，记为 $f(i,j)$。 形式化的，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有： $$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$ Doremy 对于所有的 $1 \leq j \leq i \leq n$ 写下了所有 $f(i,j)$，但是在睡了一觉后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。 保证有解。Output
**题意翻译**
Doremy有一棵边权树，她进行了 $\frac{n(n+1)}{2}$ 次实验。每次实验，她会添加一条边 $(i,j)$ ($j \leq i$)，边权为1，形成一棵基环树。然后计算每个点到环上最近点的距离，并将这 $n$ 个距离求和，记为 $f(i,j)$。
形式化地，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有：
$$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$
Doremy记录了所有 $1 \leq j \leq i \leq n$ 的 $f(i,j)$ 值，但之后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。
**题目描述**
Doremy有一个带权树，有 $ n $ 个顶点，边权是 $ 1 $ 到 $ 10^9 $ 之间的整数。她对树进行了 $ \frac{n(n+1)}{2} $ 次实验。每次实验，Doremy选择顶点 $ i $ 和 $ j $ ($ j \leq i $)，并直接用权值为1的边连接它们。这样图中就恰好有一个环（当 $ i=j $ 时是自环）。Doremy定义 $ f(i,j) $ 为从每个顶点到环上最短路径长度的总和。
形式上，设 $ \mathrm{dis}_{i,j}(x,y) $ 是在添加权值为1的边 $ (i,j) $ 后，顶点 $ x $ 和 $ y $ 之间的最短路径长度，$ S_{i,j} $ 是在添加边 $ (i,j) $ 后处于环上的顶点集合。那么，
$$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$
Doremy记下了所有 $ 1 \leq j \leq i \leq n $ 的 $ f(i,j) $ 值，然后去睡觉了。然而，醒来后她发现树不见了。幸运的是，$ f(i,j) $ 的值还在她的笔记本上，她还知道它们分别属于哪个 $ i $ 和 $ j $。给定 $ f(i,j) $ 的值，你能帮她还原这棵树吗？
保证至少存在一个合适的树。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ n $ ($ 2 \le n \le 2000 $) — 树中顶点的数量。
接下来 $ n $ 行包含一个下三角矩阵，第 $ i $ 行有 $ i $ 个整数；第 $ i $ 行的第 $ j $ 个整数是 $ f(i,j) $ ($ 0 \le f(i,j) \le 2\cdot 10^{15} $)。
保证存在一个边权在 $ 1 $ 到 $ 10^9 $ 之间的树，其 $ f(i,j) $ 的值与输入中给出的匹配。
**输出格式**
输出 $ n-1 $ 行，描述这棵树。输出的第 $ i $ 行包含三个整数 $ u_i $, $ v_i $, $ w_i $ ($ 1 \le u_i,v_i \le n $, $ 1 \le w_i \le 10^9 $)，代表一条边 $ (u_i,v_i) $，其边权是 $ w_i $。
如果有多个答案，你可以输出任何一个。
所有边必须形成一棵树，所有 $ f(i,j) $ 的值必须与输入中给出的匹配。
**输入输出样例**
**输入样例 #1**
```
3
7
3 5
0 2 8
```
**输出样例 #1**
```
2 3 3
1 2 2
```
**输入样例 #2**
```
9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748**题意翻译** Doremy有一棵边权树，她进行了 $\frac{n(n+1)}{2}$ 次实验。每次实验，她会添加一条边 $(i,j)$ ($j \leq i$)，边权为1，形成一棵基环树。然后计算每个点到环上最近点的距离，并将这 $n$ 个距离求和，记为 $f(i,j)$。 形式化地，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有： $$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$ Doremy记录了所有 $1 \leq j \leq i \leq n$ 的 $f(i,j)$ 值，但之后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。 **题目描述** Doremy有一个带权树，有 $ n $ 个顶点，边权是 $ 1 $ 到 $ 10^9 $ 之间的整数。她对树进行了 $ \frac{n(n+1)}{2} $ 次实验。每次实验，Doremy选择顶点 $ i $ 和 $ j $ ($ j \leq i $)，并直接用权值为1的边连接它们。这样图中就恰好有一个环（当 $ i=j $ 时是自环）。Doremy定义 $ f(i,j) $ 为从每个顶点到环上最短路径长度的总和。 形式上，设 $ \mathrm{dis}_{i,j}(x,y) $ 是在添加权值为1的边 $ (i,j) $ 后，顶点 $ x $ 和 $ y $ 之间的最短路径长度，$ S_{i,j} $ 是在添加边 $ (i,j) $ 后处于环上的顶点集合。那么， $$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$ Doremy记下了所有 $ 1 \leq j \leq i \leq n $ 的 $ f(i,j) $ 值，然后去睡觉了。然而，醒来后她发现树不见了。幸运的是，$ f(i,j) $ 的值还在她的笔记本上，她还知道它们分别属于哪个 $ i $ 和 $ j $。给定 $ f(i,j) $ 的值，你能帮她还原这棵树吗？ 保证至少存在一个合适的树。 **输入输出格式** **输入格式** 第一行包含一个整数 $ n $ ($ 2 \le n \le 2000 $) — 树中顶点的数量。 接下来 $ n $ 行包含一个下三角矩阵，第 $ i $ 行有 $ i $ 个整数；第 $ i $ 行的第 $ j $ 个整数是 $ f(i,j) $ ($ 0 \le f(i,j) \le 2\cdot 10^{15} $)。 保证存在一个边权在 $ 1 $ 到 $ 10^9 $ 之间的树，其 $ f(i,j) $ 的值与输入中给出的匹配。 **输出格式** 输出 $ n-1 $ 行，描述这棵树。输出的第 $ i $ 行包含三个整数 $ u_i $, $ v_i $, $ w_i $ ($ 1 \le u_i,v_i \le n $, $ 1 \le w_i \le 10^9 $)，代表一条边 $ (u_i,v_i) $，其边权是 $ w_i $。 如果有多个答案，你可以输出任何一个。 所有边必须形成一棵树，所有 $ f(i,j) $ 的值必须与输入中给出的匹配。 **输入输出样例** **输入样例 #1** ``` 3 7 3 5 0 2 8 ``` **输出样例 #1** ``` 2 3 3 1 2 2 ``` **输入样例 #2** ``` 9 8081910646 8081902766 8081903751 8081902555 8081903540 8081905228 3090681001 3090681986 3090681775 7083659398 7083657913 7083658898 7083658687 2092437133 15069617722 1748216295 1748
Doremy有一棵边权树，她进行了 $\frac{n(n+1)}{2}$ 次实验。每次实验，她会添加一条边 $(i,j)$ ($j \leq i$)，边权为1，形成一棵基环树。然后计算每个点到环上最近点的距离，并将这 $n$ 个距离求和，记为 $f(i,j)$。
形式化地，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有：
$$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$
Doremy记录了所有 $1 \leq j \leq i \leq n$ 的 $f(i,j)$ 值，但之后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。
**题目描述**
Doremy有一个带权树，有 $ n $ 个顶点，边权是 $ 1 $ 到 $ 10^9 $ 之间的整数。她对树进行了 $ \frac{n(n+1)}{2} $ 次实验。每次实验，Doremy选择顶点 $ i $ 和 $ j $ ($ j \leq i $)，并直接用权值为1的边连接它们。这样图中就恰好有一个环（当 $ i=j $ 时是自环）。Doremy定义 $ f(i,j) $ 为从每个顶点到环上最短路径长度的总和。
形式上，设 $ \mathrm{dis}_{i,j}(x,y) $ 是在添加权值为1的边 $ (i,j) $ 后，顶点 $ x $ 和 $ y $ 之间的最短路径长度，$ S_{i,j} $ 是在添加边 $ (i,j) $ 后处于环上的顶点集合。那么，
$$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$
Doremy记下了所有 $ 1 \leq j \leq i \leq n $ 的 $ f(i,j) $ 值，然后去睡觉了。然而，醒来后她发现树不见了。幸运的是，$ f(i,j) $ 的值还在她的笔记本上，她还知道它们分别属于哪个 $ i $ 和 $ j $。给定 $ f(i,j) $ 的值，你能帮她还原这棵树吗？
保证至少存在一个合适的树。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ n $ ($ 2 \le n \le 2000 $) — 树中顶点的数量。
接下来 $ n $ 行包含一个下三角矩阵，第 $ i $ 行有 $ i $ 个整数；第 $ i $ 行的第 $ j $ 个整数是 $ f(i,j) $ ($ 0 \le f(i,j) \le 2\cdot 10^{15} $)。
保证存在一个边权在 $ 1 $ 到 $ 10^9 $ 之间的树，其 $ f(i,j) $ 的值与输入中给出的匹配。
**输出格式**
输出 $ n-1 $ 行，描述这棵树。输出的第 $ i $ 行包含三个整数 $ u_i $, $ v_i $, $ w_i $ ($ 1 \le u_i,v_i \le n $, $ 1 \le w_i \le 10^9 $)，代表一条边 $ (u_i,v_i) $，其边权是 $ w_i $。
如果有多个答案，你可以输出任何一个。
所有边必须形成一棵树，所有 $ f(i,j) $ 的值必须与输入中给出的匹配。
**输入输出样例**
**输入样例 #1**
```
3
7
3 5
0 2 8
```
**输出样例 #1**
```
2 3 3
1 2 2
```
**输入样例 #2**
```
9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748**题意翻译** Doremy有一棵边权树，她进行了 $\frac{n(n+1)}{2}$ 次实验。每次实验，她会添加一条边 $(i,j)$ ($j \leq i$)，边权为1，形成一棵基环树。然后计算每个点到环上最近点的距离，并将这 $n$ 个距离求和，记为 $f(i,j)$。 形式化地，记添加边 $(i,j)$ 后环上点的集合为 $S_{i,j}$，添加后点 $(x,y)$ 之间的距离为 $\operatorname {dis}_{i,j}(x,y)$，则有： $$f(i,j)=\sum_{x=1}^{n} ( \min_{y\in S_{i,j}}\operatorname {dis}_{i,j}(x,y))$$ Doremy记录了所有 $1 \leq j \leq i \leq n$ 的 $f(i,j)$ 值，但之后忘记了这棵树。请你根据所有的 $f(i,j)$ 还原这颗树。 **题目描述** Doremy有一个带权树，有 $ n $ 个顶点，边权是 $ 1 $ 到 $ 10^9 $ 之间的整数。她对树进行了 $ \frac{n(n+1)}{2} $ 次实验。每次实验，Doremy选择顶点 $ i $ 和 $ j $ ($ j \leq i $)，并直接用权值为1的边连接它们。这样图中就恰好有一个环（当 $ i=j $ 时是自环）。Doremy定义 $ f(i,j) $ 为从每个顶点到环上最短路径长度的总和。 形式上，设 $ \mathrm{dis}_{i,j}(x,y) $ 是在添加权值为1的边 $ (i,j) $ 后，顶点 $ x $ 和 $ y $ 之间的最短路径长度，$ S_{i,j} $ 是在添加边 $ (i,j) $ 后处于环上的顶点集合。那么， $$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$ Doremy记下了所有 $ 1 \leq j \leq i \leq n $ 的 $ f(i,j) $ 值，然后去睡觉了。然而，醒来后她发现树不见了。幸运的是，$ f(i,j) $ 的值还在她的笔记本上，她还知道它们分别属于哪个 $ i $ 和 $ j $。给定 $ f(i,j) $ 的值，你能帮她还原这棵树吗？ 保证至少存在一个合适的树。 **输入输出格式** **输入格式** 第一行包含一个整数 $ n $ ($ 2 \le n \le 2000 $) — 树中顶点的数量。 接下来 $ n $ 行包含一个下三角矩阵，第 $ i $ 行有 $ i $ 个整数；第 $ i $ 行的第 $ j $ 个整数是 $ f(i,j) $ ($ 0 \le f(i,j) \le 2\cdot 10^{15} $)。 保证存在一个边权在 $ 1 $ 到 $ 10^9 $ 之间的树，其 $ f(i,j) $ 的值与输入中给出的匹配。 **输出格式** 输出 $ n-1 $ 行，描述这棵树。输出的第 $ i $ 行包含三个整数 $ u_i $, $ v_i $, $ w_i $ ($ 1 \le u_i,v_i \le n $, $ 1 \le w_i \le 10^9 $)，代表一条边 $ (u_i,v_i) $，其边权是 $ w_i $。 如果有多个答案，你可以输出任何一个。 所有边必须形成一棵树，所有 $ f(i,j) $ 的值必须与输入中给出的匹配。 **输入输出样例** **输入样例 #1** ``` 3 7 3 5 0 2 8 ``` **输出样例 #1** ``` 2 3 3 1 2 2 ``` **输入样例 #2** ``` 9 8081910646 8081902766 8081903751 8081902555 8081903540 8081905228 3090681001 3090681986 3090681775 7083659398 7083657913 7083658898 7083658687 2092437133 15069617722 1748216295 1748