如何给喜欢的明星做网站,wordpress怎么填写关键词,湖南响应式网站设计,seop算法提高之树的中心 核心思想#xff1a;树形dp 换根dp 每个点作为根节点 找其子树的最大距离和父节点的最大距离 dfs1#xff1a;求子树对于当前根节点的最大距离和次大距离 求次大距离原因#xff1a;如果当前节点是其父节点子树的最大路径上的点#xff0c;最大距离不…算法提高之树的中心 核心思想树形dp 换根dp 每个点作为根节点 找其子树的最大距离和父节点的最大距离 dfs1求子树对于当前根节点的最大距离和次大距离 求次大距离原因如果当前节点是其父节点子树的最大路径上的点最大距离不能用 dfs2找父节点以上的最长距离 #include iostream#include cstring#include algorithmusing namespace std;const int N 10010,MN1,INF0x3f3f3f3f;int n;int h[N],e[M],ne[M],w[M],idx;int d1[N],d2[N],up[N];int s1[N],s2[N]; //s1存该点最大距离从哪个点过来 s2存次大距离...void add(int a, int b, int c){e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;}void dfs1(int u,int father){for(int ih[u];~i;ine[i]){int je[i];if(j father) continue;dfs1(j,u);if(d1[j] w[i] d1[u]){d2[u] d1[u],d1[u] d1[j]w[i];s2[u] s1[u],s1[u] j;}else if(d1[j] w[i] d2[u]){d2[u] d1[j]w[i] , s2[u] j;}}}void dfs2(int u,int father){for(int ih[u];~i;ine[i]){int je[i];if(jfather) continue;//如果j为求最大距离时用的点 d1[u]不能用if(s1[u] j) up[j] w[i] max(up[u],d2[u]); else up[j] w[i] max(up[u],d1[u]);dfs2(j,u);}}int main(){memset(h,-1,sizeof h);cinn;for(int i1;in;i){int a,b,c;cinabc;add(a,b,c) , add(b,a,c);}dfs1(1,-1);dfs2(1,-1);int resINF;for(int i1;in;i) res min(res,max(d1[i],up[i]));coutresendl;}
