“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part2（A——重新定义的树的直径）

A. 点对最大值

题意：

给定一棵既有点权又有边权的树，将两点之间的权值重新定义为路径上的边权和两点的点权之和。问两点之间的最大权值。

思路：

相当于是 重新定义了树的直径，让你求解。

对于无边权的树的直径的求解：（BFS或DFS）

1.任取一点作为起点，找到距离该点最远的一个点x

2.找到距离x最远的一个点y

3.x和y之间的路径就是一条直径

关于有边权的树的直径的求解：（树形DP）

我们可以根据每一条路径上的高度最高的点来把所有路径分类，在这类内部求max，再在每一类里取max.

现在的问题就转化成了如何求出以节点x为最高点的路径的长度的最大值。

很容易可以知道，该最大值就是从节点x往下走，每一个子节点方向的路径的最大值与次大值之和。

int dfs(int u,int fa){
    int dist=0,d1=0,d2=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        int d=dfs(j,u)+w[i];
        dist=max(dist,d);
        if(d>=d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }
    ans=max(ans,d1+d2);
    return dist;
}

关于既有边权又有点权的树的直径的求解（本题）：

我们可以用dp[i]表示以i为最高点（根节点）时，只包含一个端点的权值和最大的链的的权值。

因为边权有负值，所以应当设为-inf;

代码：

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43888545

参考博客：

哈理工官方题解