← Home
For problem statement at 1000-1999/1000-1099/1020-1029/1029/problemE.txt this is a correct solution, but verifier at 1000-1999/1000-1099/1020-1029/1029/verifierE.go ends with All tests passed! can you fix the verifier? package main

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

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReader(os.Stdin)}
}

func (fs *FastScanner) nextInt() int {
	sign := 1
	val := 0
	c, _ := fs.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, _ = fs.r.ReadByte()
	}
	if c == '-' {
		sign = -1
		c, _ = fs.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, _ = fs.r.ReadByte()
	}
	return sign * val
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

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

	parent := make([]int, n+1)
	depth := make([]int, n+1)
	visited := make([]bool, n+1)
	order := make([]int, 0, n)

	// BFS from 1
	q := make([]int, 0, n)
	q = append(q, 1)
	visited[1] = true
	parent[1] = 0
	depth[1] = 0
	for head := 0; head < len(q); head++ {
		u := q[head]
		order = append(order, u)
		for _, v := range adj[u] {
			if !visited[v] {
				visited[v] = true
				parent[v] = u
				depth[v] = depth[u] + 1
				q = append(q, v)
			}
		}
	}

	covered := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		if depth[i] <= 2 {
			covered[i] = true
		}
	}

	ans := 0
	for i := len(order) - 1; i >= 0; i-- {
		u := order[i]
		if depth[u] >= 3 && !covered[u] {
			p := parent[u]
			ans++
			covered[p] = true
			for _, v := range adj[p] {
				covered[v] = true
			}
		}
	}

	fmt.Fprintln(out, ans)
}