02 树的直径问题

02 树的直径问题

做法 1. 两次 DFS

首先从任意节点 y开始进行第一次 DFS，到达距离其最远的节点，记为z，然后再从 z开始做第二次 DFS，到达距离 z最远的节点，记为 z’，则z~z’即为树的直径。

缺陷：不能处理负权边

以下代码来自OIWIKI

const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

做法2：树形dp

/ /树形dp结构伪代码描述
void dfs(节点u){
     for(){   / /循环访问所有u的子节点
     dfs(u的子节点);
     用u的子节点信息更新节点u的信息;
     }
}

二.用树形dp求树的直径：
 既然是树形动态规划，我们就尝试用上面树形dp的框架来解决问题。
1.首先，要确定维护的信息是什么？
     假设当前父节点是u ,u的所有儿子节点为 $v_{1},...,v_{n}$,那么这个信息必然要满足“只要知道了儿子节点 $v_{1},...,v_{n}$ 的该信息，就能确定 u 的该信息”。由于最终要求树上最远两个节点的距离，不妨做这样的定义：设d[x]为节点x到其子孙节点的最大距离、设f[x]为以x为根结点的一条最长路径的距离。即要维护的信息就是d[]，f[]。

2.如何维护上述信息？
(1) 假设当前遍历到的节点是u，u的子节点是v_{1},…,v_{n}，对应的边权是w_1,…,w_n.依据树形dp的“后序”思想，继续假设已经求得了u的所有子节点v_{1},…,v_{n}到其子孙节点的最大距离 d[v_{1}],…,d[v_n] 。已知信息画成下图，其中红色箭头所示的边为虚拟的边，也可看成是一条路径。

(2) 根据已知信息求d[u]:若边权都是正值,则d[u]=max(d[v_1]+w_{1},d[v_2]+w_{2},…,d[ v_n]+w_n)，若存在负的权值，则d[u]=max(0,w_1,d[v_1]+w_{1},w_2,d[v_2]+w_{2},…,w_n,d[v_n]+w_n)，可见d[u]>=0。

(3)确定f[u]的值：若边权都是正值，则f[u]=(d[ v_x]+w_x)+(d[ v_y]+ w_y ),其中(d[ v_x]+ w_x)和(d[ v_y]+w_y)分别是u能到达子孙节点的最远距离和次远距离。即f[u]=d[u]+(d[ v_y]+w_y)。

• 以上过程仅为原理解释，不作为下属程序参数和具体做法

真正的过程：
我们记录当 $1$ 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度$d_1$与次长路径（与最长路径无公共边）长度$d_2$，那么直径就是对于每一个点，该点 $d_1+d_2$ 能取到的值中的最大

#include<iostream>
#include<vector>
#define int long long
using namespace std;
class edge
{
    public:
        int point;
        int weight;
        edge(int po,int wei):point(po),weight(wei){}
};
const int N=5e5+1;
vector<edge>ipoint[N];
int d1[N],d2[N],ans=0;
int n,u,v,w;

void dfs(int nowpoint,int fa=0)
{
    d1[nowpoint]=d2[nowpoint]=0;
    for(edge ip : ipoint[nowpoint])
    {
        if(ip.point!=fa)
        {
            dfs(ip.point,nowpoint);
            int tempd=d1[ip.point]+ip.weight;
            if(tempd>d1[nowpoint])
            {
                d2[nowpoint]=d1[nowpoint];
                d1[nowpoint]=tempd;
            }
            else if(tempd>d2[nowpoint])
            {
                d2[nowpoint]=tempd;
            }
        }
    }
    ans=max(ans,d1[nowpoint]+d2[nowpoint]);

}
signed main(void)
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        ipoint[u].emplace_back(edge(v,w));
        ipoint[v].emplace_back(edge(u,w));
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

如果需要求出一条直径上所有的节点，则可以在 DP 的过程中，记录下每个节点能向下延伸的最长路径与次长路径（定义同上）所对应的子节点，在求 ans 的同时记下对应的nowpoint 节点 ，使得 $ans=d_1[nowpoint]+d_2[nowpoint]$，即可分别沿着从 nowpoint 开始的最长路径的次长路径对应的子节点一路向某个方向（对于无根树，虽然这里指定了 1为树的根，但仍需记录每点跳转的方向；对于有根树，一路向上跳即可），遍历直径上所有的节点。

OIWIKI版本代码：

const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}