← Home
For problem statement at 1000-1999/1700-1799/1790-1799/1795/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1790-1799/1795/verifierF.go ends with case 14 failed: expected 3 got 4
input:
1
7
1 7
1 4
4 2
7 3
4 6
2 5
2
1 2

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

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

	t := nextInt()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	const INF = int(1e9)

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

		k := nextInt()
		chipIdx := make([]int, n)
		for i := 1; i <= k; i++ {
			v := nextInt() - 1
			chipIdx[v] = i
		}

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

		closed := make([]bool, n)
		supply := make([]int, n)
		demand := make([]int, n)

		feasible := func(L int) bool {
			q := L / k
			r := L % k

			for i := n - 1; i >= 0; i-- {
				v := order[i]
				if chipIdx[v] > 0 {
					need := q
					if chipIdx[v] <= r {
						need++
					}
					bad := 0
					maxSup := 0
					for _, u := range adj[v] {
						if u == parent[v] {
							continue
						}
						if !closed[u] {
							bad++
						}
						if supply[u] > maxSup {
							maxSup = supply[u]
						}
					}
					if bad == 0 {
						if need == 0 {
							closed[v] = true
							demand[v] = INF
						} else {
							closed[v] = maxSup >= need
							demand[v] = need
						}
					} else {
						closed[v] = false
						demand[v] = INF
					}
					supply[v] = 0
				} else {
					bad := 0
					badChild := -1
					max1, max2, idx1 := 0, 0, -1
					for _, u := range adj[v] {
						if u == parent[v] {
							continue
						}
						if !closed[u] {
							bad++
							badChild = u
						}
						s := supply[u]
						if s > max1 {
							max2 = max1
							max1 = s
							idx1 = u
						} else if s > max2 {
							max2 = s
						}
					}

					if bad == 0 {
						closed[v] = true
						supply[v] = 1 + max1
						bestDem := INF
						for _, u := range adj[v] {
							if u == parent[v] {
								continue
							}
							if demand[u] < INF {
								rem := demand[u] - 1
								if rem > 0 && rem < bestDem {
									bestDem = rem
								}
							}
						}
						demand[v] = bestDem
					} else if bad == 1 {
						closed[v] = false
						supply[v] = 0
						bestDem := INF
						if demand[badChild] < INF {
							rem := demand[badChild] - 1
							if rem > 0 {
								bestDem = rem
								bestSup := max1
								if idx1 == badChild {
									bestSup = max2
								}
								if bestSup >= rem {
									closed[v] = true
								}
							} else {
								closed[v] = true
							}
						}
						demand[v] = bestDem
					} else {
						closed[v] = false
						supply[v] = 0
						demand[v] = INF
					}
				}
			}

			return closed[0]
		}

		lo, hi := 0, n-k+1
		for lo+1 < hi {
			mid := (lo + hi) >> 1
			if feasible(mid) {
				lo = mid
			} else {
				hi = mid
			}
		}

		out.WriteString(strconv.Itoa(lo))
		out.WriteByte('\n')
	}
}