302095: CF398C. Tree and Array
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Tree and Array
题意翻译
有一棵 $n$ 个节点的树，节点编号从 $1$ 到 $n$。树上每条边有一个边权。 定义一个数组 $t$，初始所有元素为 $0$。然后对于每条连接节点 $u$ 和 $v$ $(u<v)$，边权为 $c$ 的边，给 $t,t[u+1],\dots,t[v-1],t[v]$ 的值分别加上 $c$。 设 $d(u,v)$ 为树上节点 $u$ 和 $v$ 之间最短路的边权和。定义数对 $(x,y)$ $(1\le x<y\le n)$ 合格，当且仅当 $d(x,y)=t[x]+t[x+1]+\dots+t[y-1]+t[y]$。 对于给定的 $n$，请构造一棵这样的树，使得合格的数对至少有 $\lfloor\frac{n}{2}\rfloor$ 个。输出树的结构以及 $\lfloor\frac{n}{2}\rfloor$ 个合格的数对。如有多解，输出任意解即可。题目描述
User ainta likes trees. This time he is going to make an undirected tree with $ n $ vertices numbered by integers from $ 1 $ to $ n $ . The tree is weighted, so each edge of the tree will have some integer weight. Also he has an array $ t $ : $ t[1],t[2],...,t[n] $ . At first all the elements of the array are initialized to $ 0 $ . Then for each edge connecting vertices $ u $ and $ v $ ( $ u<v $ ) of the tree with weight $ c $ , ainta adds value $ c $ to the elements $ t,t[u+1],...,t[v-1],t[v] $ of array $ t $ . Let's assume that $ d(u,v) $ is the total weight of edges on the shortest path between vertex $ u $ and vertex $ v $ . User ainta calls a pair of integers $ x,y $ ( $ 1<=x<y<=n $ ) good if and only if $ d(x,y)=t[x]+t[x+1]+...+t[y-1]+t[y] $ . User ainta wants to make at least  good pairs, but he couldn't make a proper tree. Help ainta to find such a tree.输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 5<=n<=10^{5} $ ).
输出格式
Print $ n-1 $ lines containing the description of the edges. The $ i $ -th line should contain three space-separated integers $ u_{i},v_{i},c_{i} $ ( $ 1<=u_{i}<v_{i}<=n; 1<=c_{i}<=10^{5} $ ) — two vertices connected by the edge, and the weight of the edge. Next print  lines containing the good pairs. The $ k $ -th line should contain two space-separated integers $ x_{k} $ and $ y_{k} $ ( $ 1<=x_{k}<y_{k}<=n $ ). Of course, $ x_{k},y_{k} $ must be a good pair. All pairs should be distinct — that is, for all $ j,k $ , $ x_{j}≠x_{k} $ or $ y_{j}≠y_{k} $ must be satisfied. If there are many correct solutions, print any of them.
输入输出样例
输入样例 #1
7输出样例 #1
1 4 1
1 2 2
2 3 5
3 5 3
2 6 2
6 7 3
4 5
5 6
5 7