首先双连通缩点建立新图（顺带求原图的总的桥数，事实上因为原图是一个强连通图，所以桥就等于缩点后的边）此时得到的图类似树结构，对于新图求一次直径，也就是最长链。我们新建的边就一定是连接这条最长链的首尾，这样就将原图的桥降低了直径个。#include<iostream>#include<cstring&g...

Computer    重要性质：树上任意点能到的最远点，一定是树的直径的某个端点。 解题思路：根据上述性质，先求出树的直径，然后从直径的两个端点u和v分别DFS整棵树，对于每个结点得到两个距离d[i].u和d[i].v，二者的最大值即是i点能到的最远点的距离AC_Co...

参考：树的直径树的直径：树上最远两点（叶子结点）的距离算法：从树上任意点u开始DFS(BFS)遍历图，得到距离u最远的结点v,然后从v点开始DFS遍历图，得到距离v最远的结点w，则v、w之间的距离就是树的直径，且复杂度为2趟DFS，因此复杂度为O(n)重要性质：树上任意点能到的最远点，一定是树的直径的某个端点。模板：&...

124.BinaryTreeMaximumPathSumhttps://www.cnblogs.com/grandyang/p/4280120.html如果你要计算加上当前节点的最大path和，这个节点的左右子树必定是纯左右树(即没有拐点)，用另一个参数保留整个二叉树的最大path和，然后计算每一个以当前节点为拐点的路...

方法一计算每个节点的左子树和右子树的高度和,加上根本身(边数为2)，取最大值二叉树的最大距离，一定是经过根或者某个子树的根的路径，其两个端点必然是叶子节点或者根节点。计算二叉树的高度，并且比较经过该节点的最大距离，取最大者。其中，getTreeDistance的起点是-1，其值为二叉树的高度减1，即高度路径上的点之间的...

2019-11-03 21:37:59一、DiameterofBinaryTree问题描述：问题求解：解法一、第一反应是树上动归，每个节点保存一下左右的最大深度，最后以每个节点作为中枢计算最大的长度即可。publicintdiameterOfBinaryTree(TreeNoderoot){Map<Tr...

方法：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径证明如下：①若P已经在直径上，根据树的直径的定义可知Q也在直径上且为直径的一个端点②若P不在直径上，我们用反证法，假设此时WQ不是直径，AB是直径--->若AB与PQ有交点C，由于P到Q最远，那么PC+CQ>...