Nowcoder girl 2019： 第五题 伪直径

题目链接🔗：伪直径

题意简析

仔细阅读标题和题目之后，发现出题人又给提示了。求两条路径最长的交是多少之前，我们先想想看，树里面最长的路径可以是多少——是树的直径。但是要寻找的两条路径不能完全相同,那么在另一条路径走到最后时选择别的分叉，或者干脆把最后一条边砍掉，就得到了最大值—— 。
【 所以标题的意思是把求树的直径的模板题强行“伪”了一下，谜之感觉和第一题有异曲同工之妙 ( 比赛的时候我也没多想，直接 之后提交上去发现AK了，就跟第一题盲目 之后AK一样谜hhh ）】

复习时间

下面我们复习一下 树的直径 的求法和原理：

概念：

• 树的直径：树中最远的两个节点的距离为树的直径。

• 树上节点之间的距离：树上两个节点 、 之间的距离为从 走到 的所有路径中，边权之和的最小值。

树的直径求法

1. 当作无向图（两点之间互加一条边），用数组模拟的链表【或者结构体做的链表（不推荐）或者 vector 做的链表把图存下来】
2. 树形DP：

• 状态表示 ：
  数组 表示“以 为起点的最长链的长度”，变量 记录经过根节点（和每个“暂时”的根节点）的最长链的长度。
• 状态转移 :
  点 的所有子节点 中， 最长的子节点的链长度 ,就是 的值。( 和“吃桃”几乎一样的思路，只不过那题要记录路径 ）
• 求 ans ：
  直观来讲， 等于 最长子链 + 次长子链 + 2（ 为两个子节点分别到 的距离之和) ，那么如何用最便捷的方法得到这个值呢？我们本身就会遍历每个子节点的 ,然后把目前找的最长的更新到 里。所以，在这个过程中 被更新之前，如下等式始终存在： ，这时候求新返回的 与 的和（我们不妨多加个 直接表示 )， ，我们可以保证这两个 不是来自同一个子节点（所以一定要先计算 再更新 ！！！），而且只有找到比原先的 甚至是 还要更大的 才能更新 ，于是找到的肯定为寻找过的子链中最长链和次长链的和，因此 就是我们要找的通过点 的最长链。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010;

int h[N],ne[N],e[N],idx;// 这一行是模拟链表所需的变量
int n;// 点的总数
int st[N],d[N];// DP所需的变量，st[N]标记这个点有没有走过，d[i]表示“以i为起点的最长链的长度”
int ans;// 记录经过根节点（和每个“暂时”的根节点）的最长链的长度

// 用数组模拟链表来存图
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

// 找到以u为起点的子树的深度
void dfs(int u){
    st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(st[j]) continue;//已计算过就跳过
        dfs(j);
        ans=max(ans,d[u]+d[j]+1);// 在u为根节点时，经过u的最长链长度等于它的任意两个子节点的d[i]之和的最大值+1（ 就是找到最长和次长的子链求和再+1 ）
        d[u]=max(d[u],d[j]+1);// 所有子节点里最大的链长度+1就是父节点的最长链长度
    }
}

int main(){
    cin>>n;
    memset(h,-1,sizeof h);//初始化链表头
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;//读入相连的边
        add(b,a);
        add(a,b);
    }

    dfs(1);//随便选一点开始DP

    //找到的直径-1就是答案
    cout<<ans-1<<endl;
    return 0;
}