zcmimi's blog

arrow_back树的直径共7篇文章

avatar
zc
2020-09-10 14:05:00
查看原题

点击跳转

每次给一个叶子节点添加两个儿子,而这个叶子节点能到达的最远的点,也就是上一次求得的直径的两个端点之一

那么每添加一个点更新改点,比较直径与该点到之前直径两端的距离即可

avatar
zc
2020-02-15 20:34:00
查看原题

点击跳转

双连通分量缩点后得到的树的直径就是答案

avatar
zc
2020-01-28 01:17:00
查看原题

点击跳转

求仙人掌直径

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以考虑放n-k个节点然后使深度最大的最小

一开始的时候可以反过来想:树里面长度最大的路径就是树的直径,它的两个端点的度都是1(也就是叶子节点)

我们可以从每个叶子结点开始,向中心包围。可以用队列的方式实现。

(代码很短)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先用并查集求出所有连通块(相邻且相同颜色的节点)

接着是相邻节点的颜色都不一样的一棵树

最少次数就是树的直径/2了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

求树的直径

读入毒瘤

自己探索吧(不怀好意

(tips:getline,ssstream)

1/1
Search
search