题意：求一个 $n$ 个点的树中树的直径。

树的直径模板题。

性质

1.直径两端点一定是叶子节点。

2.距任意点最远点一定是直径的端点，据所有点最大值最小的点一定是直径的中点。

3.两棵树相连，新直径的两端点一定是原四个端点中的两个。

4.两棵树相连，设 $l$ 为树的直径长度，$q$ 为树的半径长度，$w$ 为两棵树相连的边的长度，$k$ 为直径中最接近中点的节点，新直径长度最小为 $max(max(l _1,l _2),q _1+q _2+w)\ (q=max(tot-d[k],d[k]))$。

题意：

Dark 是一张无向图，图中有 $N$ 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 $N-1$ 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 $M$ 条附加边。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

题意：

一张 $T$ 条边的无向图，点的编号为从 $1\sim 1000$，求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边(可以重复)的最短路。

虽然点为从 $1\sim 1000$，但是边只有 $100$ 条，所以可以先离散化点的编号为 $1\sim P$。

离散化后，用邻接矩阵 $A$ 存储边，所以 $A[i,j]$ 代表从 $i$ 到 $j$ 只经过一条边时的最短路。

题意：给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

考虑 Floyd 算法，$d[i,j]$ 表示经过编号不超过 $k-1$ 的节点，从 $i$ 到 $j$ 的最短路。

题意: 一个 $N$ 个点的树，树上任意两个节点的距离都是 $1$ ，一开始从 $1$ 号节点出发，经过所有边后回到 $1$ 号节点，你可以新建 $K$ 条边 $(1\leq K\leq 2)$，使得总的访问路径的长度最小，且满足新建的边正好只经过一次，输出这个最小的长度。

很明显，树上 $N$ 个点，那么就有 $N-1$ 条边，要想每个节点都访问完，根据搜索可知，总长度应为 $2(n-1)$，每条边访问一次，回溯一次。

题意：在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。现在lqr已经搞清楚黑暗城堡有 $N$ 个房间， $M$ 条可以制造的双向通道，以及每条通道的长度。lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的。但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：设 $D[i]$ 为如果所有的通道都被修建，第 $i$ 号房间与第 $1$ 号房间的最短路径长度；而 $S[i]$ 为实际修建的树形城堡第 $i$ 号房间与第 $1$ 号房间的路径长度；要求对于所有整数 $i$，有 $S[i]=D[i]$ 成立。为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。你需要输出答案对 $2^{31}-1$ 取模之后的结果。

题意：给定 $n$ 个变量，$m$ 个不等式。不等式之间具有传递性，即若 $A>B$ 且 $B>C$ ，则 $A>C$。判断这 $m$ 个不等式是否有矛盾。若存在矛盾，则求出 $t$ 的最小值，满足仅用前 $t$ 个不等式就能确定不等式之间存在矛盾。若无矛盾，则判断这 $m$ 个不等式是否能确定每一对变量之间的关系。若能，则求出 $t$ 的最小值，满足仅用前 $t$ 个不等式就能确定每一对变量之间的大小关系。

题意：大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。与首都相连的村庄将得到水资源的浇灌。他希望构建的渠道可以实现单位长度的平均成本降至最低。换句话说，渠道的总成本和总长度的比值能够达到最小。他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

题意：一个 $T$ 个点的图，有 $R$ 条双向边，$P$ 条单向边，单向边权可能为负，但保证途中不存在负环，求起点 $S$ 到各点的最短路。

很明显，带负权边，不能用 $Dijkstra$，又因为数据的特殊构造，$SPFA$ 也死了。

仔细看题目，发现“双向边都为非负的”，只有单向边可能为负权，且单向边不会构成环，那么就好办了。

题意：一个 $N$ 个点 $M$ 条边的无向图，求无向图的最小生成树，且满足 $1$ 号节点的度数不超过给定整数 $S$。

经典的最小度限制生成树问题，可以参考这位大佬的博客。

首先去掉 $1$ 号节点，则图会分成几个连通块，把每个连通块的最小生成树求出来，累计答案；

然后在每个连通块中选出一个节点 $p$ ，使得无向边 $(1,p)$ 的权值尽量小；