結果

問題 No.3113 The farthest point
ユーザー Daniel Agatan
提出日時 2025-04-19 20:15:46
言語 Go
(1.23.4)
結果
AC  
実行時間 538 ms / 2,000 ms
コード長 2,979 bytes
コンパイル時間 11,791 ms
コンパイル使用メモリ 240,524 KB
実行使用メモリ 39,432 KB
最終ジャッジ日時 2025-04-19 20:16:10
合計ジャッジ時間 21,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

/*
	By Raccoon Byte
*/

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func printf(format string, a ...interface{}) { fmt.Fprintf(writer, format, a...) }
func scanf(format string, a ...interface{})  { fmt.Fscanf(reader, format, a...) }

func getInt(num *int) {
	scanf("%d\n", num)
}

func getInt2(num *int, num2 *int) {
	scanf("%d %d\n", num, num2)
}

func getInt3(num *int, num2 *int, num3 *int) {
	scanf("%d %d %d\n", num, num2, num3)
}

func getInt4(num *int, num2 *int, num3 *int, num4 *int) {
	scanf("%d %d %d %d\n", num, num2, num3, num4)
}

func getInt5(num *int, num2 *int, num3 *int, num4 *int, num5 *int) {
	scanf("%d %d %d %d %d\n", num, num2, num3, num4, num5)
}

func getInt6(num *int, num2 *int, num3 *int, num4 *int, num5 *int, num6 *int) {
	scanf("%d %d %d %d %d %d\n", num, num2, num3, num4, num5, num6)
}

func getLine(s *string) {
	line, _ := reader.ReadString('\n')
	*s = line[:len(line)-1]
}

func getString(s *string) {
	scanf("%s\n", s)
}

func getArrInt(arr []int, n int) {
	for i := 0; i < n; i++ {
		scanf("%d", &arr[i])
	}
	scanf("\n")
}

func getArrString(arr []string, n int) {
	for i := 0; i < n; i++ {
		scanf("%s", &arr[i])
	}
	scanf("\n")
}

func printArrInt(arr []int) {
	for i := 0; i < len(arr); i++ {
		if i > 0 {
			printf(" ")
		}

		printf("%d", arr[i])
	}
	printf("\n")
}

func printArrInt2D(arr [][]int) {
	for i := 0; i < len(arr); i++ {
		printArrInt(arr[i])
	}
}

func printArrString(arr []string) {
	for i := 0; i < len(arr); i++ {
		printf("%s\n", arr[i])
	}
}

func abs(num int) int {
	if num >= 0 {
		return num
	}

	return -num
}

func min(num1 int, num2 int) int {
	if num1 <= num2 {
		return num1
	}

	return num2
}

func max(num1 int, num2 int) int {
	if num1 >= num2 {
		return num1
	}

	return num2
}

/*
	End of template
*/

func solve() {
	var n int
	getInt(&n)

	edges := map[int][][2]int{}
	var u, v, w int
	for i := 0; i < n-1; i++ {
		getInt3(&u, &v, &w)

		edges[u] = append(edges[u], [2]int{v, w})
		edges[v] = append(edges[v], [2]int{u, w})
	}

	result := 0
	isVisited := map[int]bool{}
	var dfs func(u int) (int, int)
	dfs = func(u int) (int, int) {
		maxOverAllSum := 0
		pathSums := make([]int, len(edges[u]))
		for i, e := range edges[u] {
			v, w := e[0], e[1]
			if isVisited[v] {
				continue
			}

			isVisited[v] = true
			pathSum, overallSum := dfs(v)
			pathSums[i] = max(w, w+pathSum)
			maxOverAllSum = max(maxOverAllSum, pathSums[i])
			maxOverAllSum = max(maxOverAllSum, overallSum)
		}

		sort.Ints(pathSums)
		if len(pathSums) > 1 {
			maxOverAllSum = max(maxOverAllSum, pathSums[len(pathSums)-1]+pathSums[len(pathSums)-2])
		}

		result = max(result, maxOverAllSum)
		return pathSums[len(pathSums)-1], maxOverAllSum
	}

	isVisited[1] = true
	dfs(1)
	printf("%d\n", result)
}

func main() {
	defer writer.Flush()

	tc := 1
	// getInt(&tc)
	for t := 0; t < tc; t++ {
		solve()
	}
}
0