题目链接

https://ac.nowcoder.com/acm/contest/9557/C

解题思路

代码1思路：
非严格的树上第二长路径，要么等于最长路径，要么等于最长路径-1。
当最长路径的个数多于1条的时候，答案就是最长路径，反之为最长路径-1。
num[i]表示以i为根的树最长子链的个数，d[i]表示以i为根的树最长子链的长度，sum表示最长路径的个数，mx表示最长路径的长度。
代码2思路：
保存最长路径长度和次长路径长度，保存最长子链长度和次长子链长度。
这种我只能看懂，但是理解不了细节，所以，自己看吧QWQ

两种代码的思想都是先跟新最长路径的信息再更新的最长子链的信息，读者自行理解，比较难解释。

AC代码1

const int N=1e5+10;

int cnt,head[N],mx,sum,num[N];
int d[N];

struct edge{int v,next;}e[N<<1];
void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}

void dfs(int x,int fa)
{
    num[x]=1;//！！！
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,x);

        if(d[x]+d[v]+1>mx) mx=d[x]+d[v]+1,sum=num[x]*num[v];//优先跟新以x为根树的最长路径的长度和个数
        else if(d[x]+d[v]+1==mx) sum+=num[x]*num[v];

        if(d[v]+1>d[x]) d[x]=d[v]+1,num[x]=num[v];//更新完最长路径的信息后，再更新以x为根的最长子链的长度和个数
        else if(d[v]+1==d[x]) num[x]+=num[v];
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param e int整型vector 长度为n-1的数组，表示结点2到结点n的父结点
     * @return int整型
     */
    int tree3(vector<int> a) {
        for(int i=0;i<a.size();i++){
            add(i+2,a[i]);add(a[i],i+2);
        }
        dfs(1,0);
        return sum>1?mx:mx-1;
    }
};

AC代码2

const int N=1e5+10;

int cnt,head[N],ans1,ans2;
int d[N][3];

struct edge{int v,next;}e[N<<1];
void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}

void dfs(int x,int fa)
{
    d[x][1]=0;d[x][2]=-1;//！！！
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,x);
        int t=d[v][1]+d[x][1]+1;
        if(t>=ans1) ans2=max(ans2,ans1),ans1=t;//优先更新最长路径与次长路径的长度
        else if(t>=ans2) ans2=t;
        ans2=max(ans2,max(d[x][2]+d[v][1]+1,d[x][1]+d[v][2]+1));

        t=d[v][1]+1;
        if(t>=d[x][1]) d[x][2]=max(d[x][2],d[x][1]),d[x][1]=t;//更新最长子链与次长子链的长度
        else if(t>=d[x][2]) d[x][2]=t;
        d[x][2]=max(d[x][2],d[v][2]+1);
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param e int整型vector 长度为n-1的数组，表示结点2到结点n的父结点
     * @return int整型
     */
    int tree3(vector<int> a) {
        for(int i=0;i<a.size();i++){
            add(i+2,a[i]);add(a[i],i+2);
        }
        dfs(1,0);
        return ans2;
    }
};