树的直径_牛客博客

之前写过一篇学军信友队趣味网络邀请赛 B.齐心抗疫，那篇文章中讲述了一种通过两次dfs就足以求得树的直径的方法，今天来学习另一种方法求树的直径——树形DP。

定义

树的直径：若树上两点u,vu,v间的最短路径最大，那么该路径的长度称为树的直径。（可以存在多条）

区别

两者的复杂度都是 $O(N)$
方法1：简洁方便，只用求一次即可得到树的直径，适当修改一下树的直径的两端点也可以在求树的直径的时候记录下来。
方法2：可以记录到端点的距离，有些题目会用到。

1.树形DP求树的直径

令 $f$ 数组记录当前节点不经过父节点的最长路径，显然对于当前节点 $u$ 来说他的最大值为他最大的儿子节点 $(v)$ 的 $f[v]+1$ ，这里的1表示 $edge[v][u]$ ，如果实际题目不是按1可以适当修改。
初始值：利用dfs搜到叶节点回溯，初始值 $f$ 数组清0.
转移方程： $f[u]=max(f[u],f[v]+1)$

int diam,d[N],f[N];
vector<int> G[N];

void dfs(int u,int p){
    f[u]=0;
    for(auto v:G[u]){
        if(v!=p){
            d[v]=d[u]+1;
            dfs(v,u);
            diam=max(diam,f[u]+f[v]+1);
            f[u]=max(f[u],f[v]+1);
        }
    }
}

在上述方法上进行适当修改，可以节省一个数组的空间，就变成了下面这样。

int diam,d[N];
vector<int> G[N];

int dfs(int u,int p){
    int len=0;
    for(auto v:G[u]){
        if(v!=p){
            d[v]=d[u]+1;
            int cur=dfs(v,u)+1;
            diam=max(diam,cur+len);
            len=max(len,cur);
        }
    }
    return len;
}

2.dfs求树的直径

性质：树上任意一点到树上其他点的最大最短路径一定为到两端点 $u,v$ 其中大的那一个（可以相等）。

我们写一个DFS，返回值为到给定点 $k$ 的最远点的结点编号，并用一个数组记录所有点到点 $k$ 的最短路径为多少。

1.我们先对任意一个点 $i$ 进行DFS，记录他的返回值为 $x$ ，由上述性质可知 $x$ 一定为到树的直径中的一个端点，我们同时记录了到 $i$ 的距离放入数组 $dx$ 中。
2.我们再对 $x$ 进行一次DFS，记录他的返回值 $y$ ，记录到 $x$ 的距离记录到数组 $dx$ 中。
3.最后对 $y$ 进行一次DFS，记录它的返回值 $x$ ，记录到 $y$ 的的距离到数组 $dy$ 中。

求端点和树的直径话两次dfs就够了。
之所以求三次dfs是因为第一次的距离可能是没法使用的，它记录的是到任意节点的距离。

int d1[N],d2[N];
vector<int> G[N];

int dfs(int u,int p,int *d){
    int ans=u;
    for(auto v:G[u]){
        if(v==p) continue;
        d[v]=d[u]+1;
        int now=dfs(v,u,d);
        if(d[now]>d[ans]) ans=now;
    }
    return ans;
}