泰安市住房和城乡建设委员会网站网站快速收录入口

算法提高之树的最长路径

• 核心思想：树形dp

  • 枚举路径的中间节点
  • 用f1[i] 表示i的子树到i的最长距离,f2[i]表示次长距离
  • 最终答案就是max(f1[i]+f2[i])
  • 

•   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1e4+10,M = N<<1;int n;int h[N],e[M],ne[M],w[M],idx;int f1[N],f2[N],res;void add(int a,int b,int c){e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;}void dfs(int u,int father){f1[u] = f2[u] = 0;  //当前父节点没有更新过距离for(int i=h[u];~i;i=ne[i]){int j = e[i];if(j == father) continue;  //加边的时候双向边 不能往回走dfs(j,u);  //递归//新的值比最长还大 更新次长为原最长 最长为新最长if(f1[j] + w[i] >= f1[u]) f2[u] = f1[u] , f1[u] = f1[j] + w[i];//先判断上面 再判断下面 只比次长距离长 更新次长else if(f1[j] + w[i] > f2[u]) f2[u] = f1[j]+w[i];}res = max(res,f1[u]+f2[u]);}int main(){memset(h, -1, sizeof h);cin>>n;for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}dfs(1,-1);  //随便一个点作根节点cout<<res<<endl;}