← Home
For problem statement at 0-999/200-299/280-289/288/problemD.txt this is a correct solution, but verifier at 0-999/200-299/280-289/288/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func c2(x int) int64 {
	if x < 2 {
		return 0
	}
	return int64(x) * int64(x-1) / 2
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		val := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return val
	}

	n := nextInt()
	adj := make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		u := nextInt()
		v := nextInt()
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	parent := make([]int, n+1)
	order := make([]int, 0, n)
	stack := make([]int, 1, n)
	stack[0] = 1

	for len(stack) > 0 {
		u := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		order = append(order, u)
		for _, v := range adj[u] {
			if v == parent[u] {
				continue
			}
			parent[v] = u
			stack = append(stack, v)
		}
	}

	sz := make([]int, n+1)
	for i := len(order) - 1; i >= 0; i-- {
		u := order[i]
		s := 1
		for _, v := range adj[u] {
			if v == parent[u] {
				continue
			}
			s += sz[v]
		}
		sz[u] = s
	}

	totalH := make([]int64, n+1)
	for _, u := range order {
		var sum int64
		if parent[u] != 0 {
			sum += c2(n - sz[u])
		}
		for _, v := range adj[u] {
			if v == parent[u] {
				continue
			}
			sum += c2(sz[v])
		}
		totalH[u] = sum
	}

	var ans int64
	for v := 2; v <= n; v++ {
		p := parent[v]
		t := sz[v]

		b1 := c2(t)
		if b1 != 0 {
			a1 := c2(n-t) - (totalH[p] - c2(t))
			ans += a1 * b1
		}

		t2 := n - t
		b2 := c2(t2)
		if b2 != 0 {
			a2 := c2(t) - (totalH[v] - c2(t2))
			ans += a2 * b2
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprintln(out, ans)
	out.Flush()
}