P4408 逃学的小孩-洛谷-java题解-树的直径

        题目里千万不要漏了这句话：任两个居住点间有且仅有一条通路！！！！这个条件让我们后面方便求任意一个点到其他点的距离。假设我们已经确定P,Q点为直径端点，那么PQ是必走的，CP,CQ会选取其中小的一段走，所以我们的C点要满足min(CA,CB)最大，这样就可以使答案最大。min(CP,CQ)最大的意思是，假设我们用两次dfs求得某条直径的两个端点P，Q，那么我们枚举点C，则ans=max(PQ+min(CP,CQ))。直径好求，直接套模板。因为要求端点，所以用两次搜索。然后就是求min(CP,CQ),我们可以稍微改一下树上dp求直径的模板：（下面这个我不好解释，大伙可以自己模拟一组简单的数据，就知道什么意思了）

static void dfs2(int u,int fa){
        List edges = tree.get(u);
        for(Edge edge : edges){
            if(fa==edge.v)continue;
            dis[edge.v]=dis[edge.u]+edge.w;
            dfs2(edge.v,u);
        }
    }

import java.io.*;
import java.util.*;

class Edge{
      int u;
      int v;
      int w;
      public Edge(int u,int v,int w){
          this.u=u;
          this.v=v;
          this.w=w;
      }
}

class Main {
    static int n,m;
    static long[] dis,disp,disq;
    static boolean[] vis;
    static List> tree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.nextToken();n=(int)st.nval;
        st.nextToken();m=(int)st.nval;
        dis=new long[n+1];
        disp=new long[n+1];
        disq=new long[n+1];
        vis=new boolean[n+1];
        tree=new ArrayList<>();
        for(int i=0;i<=n;i++){
            tree.add(new ArrayList());
        }
        //以上为数据输入与初始化
        int u,v,w;
        for(int i=1;i<=m;i++){
            st.nextToken();u=(int)st.nval;
            st.nextToken();v=(int)st.nval;
            st.nextToken();w=(int)st.nval;
            tree.get(u).add(new Edge(u,v,w));
            tree.get(v).add(new Edge(v,u,w));
        }
        int P=0,Q=0;        //P,Q为直径两个端点
        long ans=0,max=0;
        vis[1]=true;dfs(1); //vis[1]=true是个好习惯
        for(int i=1;i<=n;i++){
            if(dis[i]>max){
                P=i;
                max=dis[i];
            }
            dis[i]=0;
            vis[i]=false;
        }
        vis[P]=true;dfs(P);//vis[P]是个好习惯
        for(int i=1;i<=n;i++){
            if(dis[i]>ans){
                Q=i;
                ans=dis[i];
            }
            dis[i]=0;
        }
        dis=disp;dfs2(P,0);//求出P点到每一个点的距离
        dis=disq;dfs2(Q,0);
        long anss=0;
        for(int i=1;i<=n;i++){
                if(i==P||i==Q)continue;
                long temp=ans+Math.min(disp[i],disq[i]);
                anss=anss>temp?anss:temp;
        }
        System.out.println(anss);
    }
    static void dfs(int k) {                //标准两次dfs模板
        List edges = tree.get(k); 
        int len=edges.size();
        for(int i=0;i edges = tree.get(u);
        for(Edge edge : edges){
            if(fa==edge.v)continue;
            dis[edge.v]=dis[edge.u]+edge.w;
            dfs2(edge.v,u);
        }
    }
}