hk_cnyali's Blog

给你一张 $n$ 个点$m$ 条边的无向图（点从$0$到$n-1$标号），走过每条边都需要花费 $1$ 秒

给你一个整数 $k$ ，请你选择至多 $k$ 个点，令经过这些点也需要花费 $1$ 秒，使得从点 $0$ 走到点 $n-1$ 的最短时间最大，求这个最大值

注意，不能选择点 $0$ 或点

$n\le100, m\le\frac{n(n-1)}{2}$

这几天捣鼓博客，自己搞了一个新主题，速度比之前NexT快了很多

但是现在弄这个搜索框弄得我怀疑人生，鬼知道我经历了什么

索性把一些问题先留着，以后有时间了再继续调整

题面太长，放不下

用来判断两棵有根树是否同构，很简单，稍微记录一下细节(贴个代码)

我会告诉你这篇博客其实是用来测试一下自己瞎折腾的新主题的吗

有一张$n$（$n$为偶数）个点的完全图$G$，你需要为每条边确定一个不同的边权，使得这张图的最长单调上升路径边数最少

$n\le 500$

原题中还给出了一个提示：

结论：假设带权无向图 $G$ 有 $100$ 个节点 $1000$ 条边，且所有权值各不相同。那么，$G$ 中一定存在一个单调上升路径，它的长度大于等于 $20$。

证明：假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边，每次将该边连接的节点中的探险家的位置进行对调。可以知道，每个探险家都走的是一条单调上升路径。另外，由于共有 $100$ 个探险家，而探险家一共走了 $2000$ 步，所以有人走了 $20$ 步。证毕。

给出一张$n$个点$m$条边的联通图，求图的最大独立集方案数

$n\le 10^5, m\le n + 10$

给你一棵$n$个点的树，有$q$次询问。

每次询问给出一个$k$，并给出一个大小为$k$的点集$S$。求这$k$个点两两所形成的$\binom{k}{2}$条路径中：

• 所有路径长度和
• 最短路径的长度
• 最长路径的长度

$n\le 10^6, (\sum k)\le 2n$

给你一棵$n$个结点的树。

有$q$次询问，每次询问给出$k$和一个大小为$k$的点集$S$，求最少删掉多少个不在$S$中的点可以使得$S$中的点两两不联通。

无解输出$-1$

$n, q, (\sum k)\le 10^5$

给你一棵$n$个结点带边权的树。有$m$ 次询问，每次询问给出$k$，并给出一个包含 k 个点的点集 $S$

求将点集$S$与 $1$ 号点切断最小的代价

$n \le 2.5 \times 10^5, m \ge 1, \sum k \le 5 \times 10^5$