本文共 998 字，大约阅读时间需要 3 分钟。

【题意】

给定一棵树，两个结点之间的距离为树上路径的长度，要求构造一棵树上所有边的权值和最大的树并输出权值。

【题解】

我们可以把这个问题转化成，求每个结点的树上最长路径再加入到新构造的树中，注意n个长度求和后要删去最长边，因为最长的路径被重复计数了而我们只需要n-1条边。

那么树上最长路径怎么求呢？

可以看出，离第i个结点最远的距离，是边（v,i）的长度（其中v是i 的父亲）加上第v个结点删去i这棵子树之后可以得到的v的最长距离，与i在i的所有子树中可以获得的最大距离 这两者之间的最大值。

那么我们可以令

dp[v][0]:表示v的孩子最长距离（也就是v在v的所有子树中可以获得的最大距离） 

dp[v][1]:表示v的孩子第二长距离（这是用来求父亲最长距离的） 

dp[v][2]:表示v的父亲最长距离（也就是v往上走找最大距离的时候可以获得的最大值）

dp[v][0]可以通过一次深搜得到，每次搜索时要用数组id[v]记录v这个节点的孩子最长距离中，经过的第一个孩子。然后再做一次深搜，跳过id[v]再进行比较就可以得到dp[v][1]了。id[v]还有一个作用，就是防止父节点v在跑孩子最长距离时跑到节点i的子树中。我们如果需要求离结点i的最长的结点的距离，而v是i的父亲，假设i往它所有子树走都不是最大距离的时候，那么i的最大距离应该是先往v走一步，然后再求出v的最大距离（而且不能经过i）。而假如v可以在它的子树中找到最大值时，刚好i又在这条路径里，那么就需要跳过i这条路径，然后看下子树中第二长的路径和v再往v的父亲走一步两者之间的较大值，重复相同过程就可以得到最后的结果。 

但是每个节点都这么走一趟的话，时间复杂度会是O(n^2)。而向上走的距离是可以直接记录下来的，深搜一下就可以得到了。那么最后的结果就是 max(dp[i][0],dp[i][2])。

总体时间复杂度O(n)。

【代码】

#include 
   
    using namespace std;const int maxn=1e5+5;typedef long long ll;vector 
    
      p[maxn],val[maxn];ll dp[3][maxn],id[maxn];void dfs1(int x,int f) //更新子树的最大和与次大和{    for(int i=0;i
    
   

转载地址：http://phfen.baihongyu.com/