题解 | #最长路径#

一.题目描述
NC537最长路径
城市A新建了n个座房子，城市规划处用n−1条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。
二.算法(dfs)

题目意思我们理解后，我们知道要求求出两个房子直接的最长距离，在图论中被叫做图的直径。对于直径的求法，我们可以从结点的度为1的点开始搜索，在搜索过程中不断维护最大值，进而求出最长路径，下面是完整代码：

class Solution {
#define pi pair<int, int>
#define ll long long
private:
    ll ans;//在搜索中不断维护ans 保证ans是最大值
    vector<pi> mp[100005];
public:
    //st表示当前点可以到大的点，ed表示搜索的上一个点，sum表示价值和
    void dfs(int st, int ed,ll sum = 0) {
        for (int i=0;i<mp[st].size();i++){
            int nx=mp[st][i].first;
            int w=mp[st][i].second;
            if (nx==ed) continue;
            ans=max(sum+w,ans);
            dfs(nx,st,sum+w); 
        }
    }
    ll solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        //利用二维vector进行存图
        for (int i=0;i<n-1; ++i){
            //双向边
            mp[u[i]].push_back({v[i], w[i]});
            mp[v[i]].push_back({u[i], w[i]});
        }
        //找到每一个度只有1的结点作为起点进行搜索
        for (int i=1;i<=n;i++){
            if (mp[i].size()==1)
                dfs(i,i, 0);
        }
        return ans;//返回结果即可
    }
};

时间复杂度： 对每一个结点都dfs一次
空间复杂度： 在搜索过程中需要开辟二维数组来存储图
优缺点：便于实现思路简单，但是时间效率不高。
三.算法(java的实现)
对于前者的c++写法我们很容易理解，下面我们将提供java的写法，看题解Java写的人很少，为了照顾一下java选手(博主也是个java新手)。下面给出完整代码：

import java.util.*;
import java.util.*;
public class Solution {
    //这块也是博主问了别人才知道的 和C++差的蛮多的
    //首先是先声明后赋予对象 而且都基于static
    private static final int[] nx,h,e,wu,cn;
    private static int cnt;
    private static int ans;
    //都是静态变量
    static {
        //在静态代码块里面对静态变量进行赋值
        ans=0;
        nx =new int[10005];
        h=new int[10005];
        e= new int[100005];
        wu=new int[100005];
        cn=new int[100005];
        cnt=0;
    }
    public long solve (int n, int[] u, int[] v, int[] w) {
        for(int i=0;i<n-1;i++){
            add(u[i],v[i],w[i]);
            add(v[i],u[i],w[i]);
            cn[u[i]]++;
            cn[v[i]]++;
        }
        for(int i=1;i<=n;i++){
            if(cn[i]==1){
                dfs(i,i,0);
            }
        }
        return ans;
    }
    //st表示当前点可以到大的点，ed表示搜索的上一个点，sum表示价值和
    void dfs(int st, int ed,long sum) {
        for(int i=h[st];i!=0;i=nx[i]) {
            int next=e[i];
            long ww=wu[i];
            //next表示下一个可以到达的点
            //wu表示边权
            if (next==ed) continue;//和前一个点之间跳过 避免重复搜索
            ans=(int)Math.max(sum+ww,ans);
            dfs(next,st,sum+ww);
        }
    }
    //用数组来模拟 链式前向星
    void add(int a,int b,int c){
        e[cnt]=b;
        wu[cnt]=c;
        nx[cnt]=h[a];
        h[a]=cnt++;
    }
}

时间复杂度： 对每一个结点都dfs一次
空间复杂度： 在搜索过程中利用链式前向星进行存图
优缺点：在思路大致相同的情况下，java的写法相比于c++麻烦很多。