← Home
For problem statement at 1000-1999/1700-1799/1700-1709/1702/problemG1.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1700-1709/1702/verifierG1.go ends with output line count mismatch

exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"io"
	"os"
)

const LOG = 20

var up [][]int
var depth []int

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val
}

func lca(a, b int) int {
	if depth[a] < depth[b] {
		a, b = b, a
	}
	diff := depth[a] - depth[b]
	i := 0
	for diff > 0 {
		if diff&1 == 1 {
			a = up[i][a]
		}
		diff >>= 1
		i++
	}
	if a == b {
		return a
	}
	for i = LOG - 1; i >= 0; i-- {
		if up[i][a] != up[i][b] {
			a = up[i][a]
			b = up[i][b]
		}
	}
	return up[0][a]
}

func dist(a, b int) int {
	c := lca(a, b)
	return depth[a] + depth[b] - 2*depth[c]
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()

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

	up = make([][]int, LOG)
	for i := 0; i < LOG; i++ {
		up[i] = make([]int, n+1)
	}
	depth = make([]int, n+1)

	queue := make([]int, 0, n)
	queue = append(queue, 1)
	for head := 0; head < len(queue); head++ {
		v := queue[head]
		for _, to := range adj[v] {
			if to == up[0][v] {
				continue
			}
			up[0][to] = v
			depth[to] = depth[v] + 1
			queue = append(queue, to)
		}
	}

	for j := 1; j < LOG; j++ {
		prev := up[j-1]
		cur := up[j]
		for v := 1; v <= n; v++ {
			cur[v] = prev[prev[v]]
		}
	}

	q := fs.NextInt()
	var out bytes.Buffer

	for ; q > 0; q-- {
		k := fs.NextInt()
		p := make([]int, k)
		for i := 0; i < k; i++ {
			p[i] = fs.NextInt()
		}

		if k <= 2 {
			out.WriteString("YES\n")
			continue
		}

		s := p[0]
		a := s
		best := -1
		for _, x := range p {
			d := dist(s, x)
			if d > best {
				best = d
				a = x
			}
		}

		b := a
		best = -1
		for _, x := range p {
			d := dist(a, x)
			if d > best {
				best = d
				b = x
			}
		}
		dab := best

		ok := true
		for _, x := range p {
			if dist(a, x)+dist(x, b) != dab {
				ok = false
				break
			}
		}

		if ok {
			out.WriteString("YES\n")
		} else {
			out.WriteString("NO\n")
		}
	}

	os.Stdout.Write(out.Bytes())
}