题目描述

看了很久终于看懂了，向下的方式好求，只是要维护两个数组最长路径经过的节点p1，次长路径经过的节点p2
向上的情况可分为三种情况
1. 巧了，正好向上找了，那up[u]=up[f]+wuf
2. 不太巧，往下找了，但找的不是最长路径,综合1，2两种情况，up[u]就等max(d1[u],up[u])+w[i]
3. 更不太巧，往下找了，且找的是最长路径，这样只能用次长路径更新

先做down，再做up

#include <iostream>
#include <cstring>

using namespace std;

const int N=10010;

//两类，向上走，向下走
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int d1[N],d2[N],up[N];
int p1[N],p2[N];

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

int dfs_down(int u,int fa)
{

    //注意初始化！！
    d1[u]=d2[u]=-0x3f3f3f3f;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;

        int d=dfs_down(j,u)+w[i];
        if(d>=d1[u])
        {
            d2[u]=d1[u],d1[u]=d;
            p2[u]=p1[u],p1[u]=j;
        }
        else if(d>d2[u])
        {
            d2[u]=d;
            p2[u]=j;
        }

    }

    //如果是叶子节点，返回0！！
    if(d1[u]==-0x3f3f3f3f) d1[u]=d2[u]=0;
    return d1[u];
}

void dfs_up(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;

        if(p1[u]==j)
        {
            up[j]=max(up[u],d2[u])+w[i];
        }
        else
        {
            up[j]=max(up[u],d1[u])+w[i];
        }
        dfs_up(j,u);
    }
}

int main()
{
    int n;
    memset(h,-1,sizeof h);
    cin>>n;
    int m=n;
    n--;
    while(n--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs_down(1,-1);
    dfs_up(1,-1);

    int res=0x3f3f3f3f;
    for(int i=1;i<=m;i++)
    {
        res=min(res,max(d1[i],up[i]));
    }
    cout<<res;
    return 0;
}

二刷

#include <iostream>
#include <cstring>

using namespace std;

const int N=10010;

//两类，向上走，向下走
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int d1[N],d2[N],up[N];
int p1[N],p2[N];

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

int dfs_down(int u,int fa)
{

    d1[u]=d2[u]=-0x3f3f3f3f;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs_down(j,u)+w[i];
        if(d>=d1[u])
        {
            d2[u]=d1[u];
            p2[u]=p1[u];
            d1[u]=d;
            p1[u]=j;
        }
        else if(d>d2[u])
        {
            d2[u]=d;
            p2[u]=j;
        }
    }
    if(d1[u]==-0x3f3f3f3f) d1[u]=d2[u]=0;
    return d1[u];
}

int dfs_up(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        if(p1[u]==j)
        {
            up[j]=max(up[u],d2[u])+w[i];
        }
        else
        {
            up[j]=max(up[u],d1[u])+w[i];
        }
        dfs_up(j,u);
    }
}
int main()
{
    int n;
    memset(h,-1,sizeof h);
    cin>>n;
    int m=n;
    n--;
    while(n--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs_down(1,-1);
    dfs_up(1,-1);

    int res=0x3f3f3f3f;
    for(int i=1;i<=m;i++)
    {
        res=min(res,max(d1[i],up[i]));
    }
    cout<<res;
    return 0;

}

三刷，还是不会。。。

看了一遍自己一刷的总结看懂了，
再总结一下：
1. 向下找时要维护次长最长两条路径，且要记录次长和最长的下一个节点
2. 向上找时，每次更新的是up[j]而不是up[u],用up[u]来更新up[j]

#include <iostream>
#include <cstring>

using namespace std;

const int N=100010;
int e[N*2],ne[N*2],w[N*2],idx,h[N];

int n;
int ans=0x3f3f3f3f;

int d1[N],d2[N],up[N]; 
int p1[N],p2[N];

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

int dfs(int u,int fa)
{
    int dist=0;
    d1[u]=d2[u]=-0x3f3f3f3f;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs(j,u)+w[i];


        if(d>=d1[u])
        {
            d2[u]=d1[u];
            d1[u]=d;
            p2[u]=p1[u];
            p1[u]=j;
        }
        else if(d>d2[u])
        {
            d2[u]=d;
            p2[u]=j;
        }

    }
    if(d1[u]==-0x3f3f3f3f) d1[u]=d2[u]=0;
    return d1[u];
}

void dfs_up(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        //注意这里计算的是up[j]而不是up[u]
        //up[j]的取值有三种情况：1. up[u]  2. 当p1[u]!=j时，取d1[u] 3. d2[u] 
        if(p1[u]==j)
        {
            up[j]=max(up[u],d2[u])+w[i];
        }
        else
        {
            up[j]=max(up[u],d1[u])+w[i];
        }
        dfs_up(j,u);
    }

}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    dfs_up(1,-1);
    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        res=min(res,max(d1[i],up[i]));
    }
    cout<<res;
    return 0;
}