[FJWC2019 Day2] 直径

时间限制：1000MS      内存限制：524288KB

难度： \(4.0\)

• 题目描述

你需要构造一棵至少有两个顶点的树，树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。

我们定义这棵树的直径为，所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中，\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\)，那么均为直径。

作为一个构造题，你需要构造一个恰有 \(k\) 个直径的树。可以证明在给定的限制下一定有解。

• 输入格式

一行一个正整数 \(k\)，表示你需要构造出一个恰有 \(k\) 个直径的树。

• 输出格式

第一行一个正整数 \(n\)，表示你构造的树的点数。

接下来 \(n-1\) 行，每行三个整数 \(i,j,w\)，表示一条连接点 \(i\) 和 \(j\) （点的编号为 \(1,2, \cdots, n\)）的树边，边权为 \(w\) 。

• 样例输入

• 样例输出

• 样例说明

这只是一种符合题意的输出，可能还有其他输出。在这个输出中，直径为 \((1,5),(3,5),(4,5)\) 。

• 数据规模与约定

注意，你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\) ！

对于 \(30pts\) 的数据，\(1\leq k \leq 2000\) ；

对于 \(100pts\) 的数据，\(1\leq k \leq 5 \times 10^6\) 。

 

 

YZOJ P4260

---

 

 

 

大部分人都当场切掉了，我没有一个清醒的思路就没有构造出来。。。

首先，样例是一个菊花。可以很容易发现，要构造出 \(k\) 条直径，只需要按照下图的方案：

这样就是用 \(k+2\) 个点构造出一个菊花，显然有 \(k\) 条最长链，拿到 \(30pts\) 。

 

因为 \(2 \leq n \leq 5000\) ，\(k\) 很大，所以考虑将 \(k\) 进行分解。我当时就想到可以往点外连 \(a\) 条边权为 \(1\) ， \(b\) 条边权为 \(2\) 形成的菊花，这样答案就是 \(k=a \times b\) ，可以把 \(k\) 变小。但是这样做的话万一 \(k\) 是个大质数，那又完蛋了，没有办法分解。

然而到这里我就想不下去了。其实离正解只差一步之遥：\(k\) 分解的还不够。

考虑向外连三个菊花（如下图），这样 \(k=ab+ac+bc\) 。

这样子就有办法分解了！

\(k=ab+ac+bc=a(b+c)+bc\) ，即 \(a=\frac{k-bc}{b+c}\) 。由于 \(a+b+c \leq n-4\) ，所以可以直接暴力枚举 \(b, c\) 然后算出合法的 \(a\) ，这样就得到了一组合法的构造方案了，时间复杂度 \(O(n^2)\) 。

此外，本题还可以利用边权为 \(0\) 的性质挂链，或者其他一些奇奇怪怪的做法。