算法提高之树的中心

算法提高之树的中心

• 核心思想：树形dp + 换根dp

  • 每个点作为根节点 找其子树的最大距离和父节点的最大距离

  • dfs1：求子树对于当前根节点的最大距离和次大距离

    • 求次大距离原因：如果当前节点是其父节点子树的最大路径上的点，最大距离不能用
    • 

  • dfs2：找父节点以上的最长距离

•   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 10010,M=N<<1,INF=0x3f3f3f3f;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 i=h[u];~i;i=ne[i]){int j=e[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 i=h[u];~i;i=ne[i]){int j=e[i];if(j==father) 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);cin>>n;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c) , add(b,a,c);}dfs1(1,-1);dfs2(1,-1);int res=INF;for(int i=1;i<=n;i++) res = min(res,max(d1[i],up[i]));cout<<res<<endl;}