「CF804D」Expected diameter of a tree-树的直径+乱搞

给定一个含有 $n$ 个点, $m$ 条边的森林。有 $q$ 个询问,每次给出两个点 $u_i,v_i$ ,如果 $u_i$ 在联通块 $A$ 内,$v_i$ 在联通块 $B$ 内,我们随机选择两个点 $a \in A,b \in B$ ,我们在 $(a,b)$ 之间连一条边,如果这个连接成后新联通块不构成一个树,输出 $-1$ ,否则输出新联通块树的直径的期望。所有边权均为 $1$ 。

「CF379F」New Year Tree-树的直径-倍增

你是一个程序猿,现在有一棵新年树(并不是传统的带着叶子的树)——它有四个节点: $1$ ,$2$ ,$3$ ,$4$ . 其中$2$ ,$3$ ,$4$ 的父亲都是 $1$ .

新年里,程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的:

  1. 找到树上的一个叶子结点 $v$ .
  2. 设现在树上有 $n$ 个节点,那么你现在会加入两个节点$n+1$ 和 $n+2$ ,它们都会成为 $v$ 的儿子.

你的任务是在做 $q$ 次这样的操作,并在每做完一次后计算一次树的直径。来吧,我们一起来解决这道新年问题吧!

「SDOI2011」消防-树的直径+单调队列

某个国家有$n$个城市,这$n$个点之间的边构成一棵树。

现求一条边长度和不超过$S$的路径(两端都是城市,可以只为一个城市),使得所有城市到这条路径的距离的最大值最小,并输出这个最小值。

「SDOI2013」直径-树的直径

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵$n$个结点的树,求其直径的长度,以及有多少条边满足所有的直径都经过该边。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×