Constructing

题目 题意 给定一颗树，每个点有点权。求有多少对点对 \((x,y)\) 满足 \(x<y\) 且以 \(x\) 到 \(y\) 的简单路径上的所有点的点权作为边长，能围成一个凸多边形。 \(1 \leq n \leq 10^5\)，\(1 \leq a_i \leq 10^9\)。 思路 遇到这种 ......

很trivial的构造题 首先上来判掉一些显然无解的情况，然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来 考虑在链上接一些点使得直径不会变长，对于链上的某个点，它最多能接上的链的长度就是它到两个端点距离的最小值 不妨设计递归函数求解，设solve(x,dis,lim)表示在 ......

CF1003E - Tree Constructing 题目传送门 知识点：贪心 题意 给定 \(n\) 个顶点，问是否能够构造出一棵直径为 \(d\) 的树，且每个顶点的度数最多为 \(k\) 。 思路 我们要构造出一棵树，使得其直径长度一定为 \(d\) ，那么我们可以先选择 \(d + 1\) ......