原题链接

ACwing

思路

显然，所求就是树的直径。求树的直径一般有两种方法，大家熟知的是通过两次bfs（或者dfs）求解的方法，此处给出使用树形DP的解法。

所谓的树直径，实际上就是求树中通过任意一个节点的最长链。为了求解过任意一个点的最长链大小，我们首先求解任意一个节点到其任意一个子树中叶节点的最长路径大小；显然，通过一个简单的DFS即可完成求解，我们不妨记为节点到其子树中叶节点的最大距离。

在此基础上，对于任何一个节点，过它的最长链实际上就是。

问题到这里，似乎已经解决了——首先通过一个DFS, 求解，然后在通过一个DFS，内嵌一个双层循环，求解每一个节点的最长链，然而，这样的时间复杂度并不是一开始提到方法的线性。

实际上，在求解时，遍历到第i的节点时，此时的。故而，整个求解过程只需要一次遍历，复杂度是线性的。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 +10;
const int M = 100000 +10;
int tot;
int head[N], ver[M], edge[M], Next[M];
int dp[N];
bool vis[N];
int ans = 0;

void Init(){
    tot = 0;
    memset(head, 0, sizeof head);
    memset(ver, 0, sizeof ver);
    memset(edge, 0, sizeof edge);
    memset(Next, 0, sizeof Next);
    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof vis);
}

void Add(int x, int y, int edge_val){
    ver[++tot] = y, edge[tot] = edge_val , Next[tot] = head[x];
    head[x] = tot;
}

void Dfs(int x){
    vis[x] = true;
    
    for(int i = head[x];i;i = Next[i]){
        int cur_ver = ver[i];
        int edge_val = edge[i];
        if (vis[cur_ver])continue;
        Dfs(cur_ver);
        ans = max(ans, dp[x] + dp[cur_ver] + edge_val);
        dp[x] = max(dp[x], dp[cur_ver] + edge_val);
    }
}


int main(){
    int m,n;
    cin>>m>>n;
    for(int i=0;i<m-1;i++){
        int node;
        cin>>node;
        Add(i+2, node,1);
        Add(node, i+2,1);
    }
    
    for(int i=0;i<n;i++){
        int node;
        cin>>node;
        Add(m+1+i, node, 1);
        Add(node, m+1+i,1);
    }
    
    Dfs(1);
    cout<<ans<<endl;
    return 0;
}