結果

問題 No.3113 The farthest point
ユーザー 37zigen
提出日時 2025-04-19 15:17:49
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,689 ms / 2,000 ms
コード長 1,985 bytes
コンパイル時間 2,905 ms
コンパイル使用メモリ 89,076 KB
実行使用メモリ 96,052 KB
最終ジャッジ日時 2025-04-19 15:18:32
合計ジャッジ時間 35,715 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 512 * 1024 * 1024).start();
    }
    int N;
    ArrayList<Edge>[]g;
    long[] height=new long[200000];
    int[] dp2=new int[200000];
    class Edge {
    	int v;
    	long cost;
    	public Edge(int v, long cost) {
    		this.v=v;
    		this.cost=cost;
    	}
    }
    
    long ans=0;
    
    void dfs(int v, int p) {
    	for(Edge e:g[v]) {
    		if(e.v==p)continue;
    		dfs(e.v,v);
    		height[v]=Math.max(height[v], height[e.v]+e.cost);
    	}
    }
    
    void dfs2(int v, int p, long up) {
    	long[]L=new long[g[v].size()];
    	long[]R=new long[g[v].size()+1];
    	for(int i=0;i<g[v].size();++i) {
    		if(i>0)L[i]=L[i-1];
    		Edge e=g[v].get(i);
    		int u=e.v;
    		if(u==p)continue;
    		L[i]=Math.max(L[i], height[u]+e.cost);
    	}
    	for(int i=g[v].size()-1;i>=0;--i) {
    		R[i]=R[i+1];
    		Edge e=g[v].get(i);
    		int u=e.v;
    		if(u==p)continue;
    		R[i]=Math.max(R[i], height[u]+e.cost);
    	}
    	for(int i=0;i<g[v].size();++i) {
    		Edge e=g[v].get(i);
    		int u=e.v;
    		if(u==p)continue;
    		ans=Math.max(ans,L[i]+R[i+1]);
    	}
    	for(int i=0;i<g[v].size();++i) {
    		Edge e=g[v].get(i);
    		int u=e.v;
    		if(u==p)continue;
    		dfs2(u, v, Math.max(up,Math.max(L[i],R[i+1])+e.cost));
    	}
    }
    
    public void run() {
    	Scanner sc=new Scanner(System.in);
    	N=sc.nextInt();
    	g=new ArrayList[N];
    	for(int i=0;i<N;++i)g[i]=new ArrayList<>();
    	for(int i=0;i<N-1;++i) {
    		int u=sc.nextInt()-1;
    		int v=sc.nextInt()-1;
    		long w=sc.nextLong();
    		g[u].add(new Edge(v,w));
    		g[v].add(new Edge(u,w));
    	}
    	dfs(0,-1);
    	dfs2(0, -1, 0);
    	System.out.println(ans);
    }
    
    void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}
0