暴力做法，两次dfs求树的直径，只适用于无负权边的情况

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5+10,M = N * 2;
int q;
int depth[N];
int fa[N][16];
int h[N],e[M],ne[M],idx;
int dist[N];
int n = 4;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int u,int fa,int dis)
{
    dist[u] = dis;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == fa)continue;
        dfs(j,u,dis+1);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin>>q;
    for(int i = 2;i<=4;i++)
    {
        add(1,i);
        add(i,1);
    }

    while(q--)
    {
        int v;
        cin>>v;

        add(v,n+1);add(n+1,v);
        add(v,n+2);add(n+2,v);

        n+=2;

        dfs(1,-1,0);
        int u = 1;
        for(int i = 1;i<=n;i++)
        {
            if(dist[i] > dist[u])u = i;
        }
        dfs(u,-1,0);
        for(int i = 1;i<=n;i++)
        {
            if(dist[i] > dist[u])u = i;
        }
        cout<<dist[u]<<endl;
    }
    return 0;
}

正解

直径只有三种情况，假设原来直径为ab,新加的叶节点为xy

1）ab 2)ax 3)bx ,利用lca快速求出距离即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010,K = 20;
int depth[N],fa[N][K];

int lca(int a,int b)
{
    if(depth[a] < depth[b])swap(a,b);
    for(int k = K-1;k>=0;k--)
    {
        if(depth[fa[a][k]] >= depth[b])a = fa[a][k];
    }
    if(a == b)return a;
    for(int k = K-1;k>=0;k--)
    {
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

int get_dist(int a,int b)
{
    int p = lca(a,b);
    return depth[a] + depth[b] - 2 * depth[p];
}

int main()
{
    int q;
    cin>>q;
    for(int i = 2;i<=4;i++)
    {
        depth[i] = 1;
        fa[i][0] = 1;
    }
    int n = 4;

    int A = 2,B = 3,res = 2;

    while(q--)
    {
        int v;
        cin>>v;

        int x = n + 1,y = n + 2;
        n += 2;


        fa[x][0] = fa[y][0] = v;
        depth[x] = depth[y] = depth[v] + 1;
        for(int i = 1;i<K;i++)
        {
            fa[x][i] = fa[fa[x][i-1]][i-1];
            fa[y][i] = fa[fa[y][i-1]][i-1];
        }

        int da = get_dist(A,x),db = get_dist(B,x);
        if(da > db && da > res)res = da,B = x;
        else if(da <= db && db >res)res = db,A = x;
        cout<<res<<endl;
    }
    return 0;
}