← Home
For problem statement at 1000-1999/1900-1999/1970-1979/1975/problemE.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1970-1979/1975/verifierE.go ends with empty input
exit status 1 can you fix the verifier? ```go
package main

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

const LOG = 20

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

	var t int
	fmt.Fscan(in, &t)
	for tc := 0; tc < t; tc++ {
		var n, q int
		fmt.Fscan(in, &n, &q)
		color := make([]int, n+1)
		for i := 1; i <= n; i++ {
			fmt.Fscan(in, &color[i])
		}
		adj := make([][]int, n+1)
		for i := 0; i < n-1; i++ {
			var x, y int
			fmt.Fscan(in, &x, &y)
			adj[x] = append(adj[x], y)
			adj[y] = append(adj[y], x)
		}

		up := make([][]int, n+1)
		for i := range up {
			up[i] = make([]int, LOG)
		}
		depth := make([]int, n+1)
		tin := make([]int, n+1)
		vertAtTime := make([]int, n+1)
		time := 0

		var dfs func(int, int)
		dfs = func(v, p int) {
			time++
			tin[v] = time
			vertAtTime[time] = v
			up[v][0] = p
			for i := 1; i < LOG; i++ {
				up[v][i] = up[up[v][i-1]][i-1]
			}
			for _, to := range adj[v] {
				if to != p {
					depth[to] = depth[v] + 1
					dfs(to, v)
				}
			}
		}
		dfs(1, 1)

		lca := func(u, v int) int {
			if depth[u] < depth[v] {
				u, v = v, u
			}
			for i := LOG - 1; i >= 0; i-- {
				if depth[u]-(1<<i) >= depth[v] {
					u = up[u][i]
				}
			}
			if u == v {
				return u
			}
			for i := LOG - 1; i >= 0; i-- {
				if up[u][i] != up[v][i] {
					u = up[u][i]
					v = up[v][i]
				}
			}
			return up[u][0]
		}

		dist := func(u, v int) int {
			w := lca(u, v)
			return depth[u] + depth[v] - 2*depth[w]
		}

		bit := make([]int, n+2)
		bitAdd := func(idx, delta int) {
			for idx <= n {
				bit[idx] += delta
				idx += idx & -idx
			}
		}
		bitSum := func(idx int) int {
			res := 0
			for idx > 0 {
				res += bit[idx]
				idx -= idx & -idx
			}
			return res
		}
		bitFindKth := func(k int) int {
			idx := 0
			bitMask := 1
			for bitMask <= n {
				bitMask <<= 1
			}
			for i := bitMask; i > 0; i >>= 1 {
				next := idx + i
				if next <= n && bit[next] < k {
					k -= bit[next]
					idx = next
				}
			}
			return idx + 1
		}

		active := make([]bool, n+1)
		cnt := 0
		var curSum int64 = 0

		for i := 1; i <= n; i++ {
			if color[i] == 1 {
				u := i
				pos := tin[u]
				total := bitSum(n)
				preSum := bitSum(pos - 1)
				curSumBIT := bitSum(pos)
				var p, s int = -1, -1
				if preSum > 0 {
					p = vertAtTime[bitFindKth(preSum)]
				}
				if curSumBIT < total {
					s = vertAtTime[bitFindKth(curSumBIT + 1)]
				}

				if p == -1 && s == -1 {
				} else if p == -1 {
					f := vertAtTime[bitFindKth(1)]
					curSum += int64(dist(u, s) + dist(f, u) - dist(f, s))
				} else if s == -1 {
					l := vertAtTime[bitFindKth(total)]
					curSum += int64(dist(p, u) + dist(u, l) - dist(p, l))
				} else {
					curSum += int64(dist(p, u) + dist(u, s) - dist(p, s))
				}

				bitAdd(pos, 1)
				active[u] = true
				cnt++
			}
		}

		for i := 0; i < q; i++ {
			var u int
			fmt.Fscan(in, &u)
			pos := tin[u]
			if active[u] {
				total := bitSum(n)
				preSum := bitSum(pos - 1)
				rank := bitSum(pos)
				var p, s int = -1, -1
				if preSum > 0 {
					p = vertAtTime[bitFindKth(preSum)]
				}
				if rank < total {
					s = vertAtTime[bitFindKth(rank + 1)]
				}

				if p == -1 && s == -1 {
					curSum = 0
				} else if p == -1 {
					l := vertAtTime[bitFindKth(total)]
					curSum -= int64(dist(u, s) + dist(l, u) - dist(l, s))
				} else if s == -1 {
					f := vertAtTime[bitFindKth(1)]
					curSum -= int64(dist(p, u) + dist(u, f) - dist(p, f))
				} else {
					curSum -= int64(dist(p, u) + dist(u, s) - dist(p, s))
				}

				bitAdd(pos, -1)
				active[u] = false
				cnt--
			} else {
				total := bitSum(n)
				preSum := bitSum(pos - 1)
				curSumBIT := bitSum(pos)
				var p, s int = -1, -1
				if preSum > 0 {
					p = vertAtTime[bitFindKth(preSum)]
				}
				if curSumBIT < total {
					s = vertAtTime[bitFindKth(curSumBIT + 1)]
				}

				if p == -1 && s == -1 {
				} else if p == -1 {
					f := vertAtTime[bitFindKth(1)]
					curSum += int64(dist(u, s) + dist(f, u) - dist(f, s))
				} else if s == -1 {
					l := vertAtTime[bitFindKth(total)]
					curSum += int64(dist(p, u) + dist(u, l) - dist(p, l))
				} else {
					curSum += int64(dist(p, u) + dist(u, s) - dist(p, s))
				}

				bitAdd(pos, 1)
				active[u] = true
				cnt++
			}

			if cnt > 0 && curSum == int64(2*cnt-2) {
				fmt.Fprintln(out, "Yes")
			} else {
				fmt.Fprintln(out, "No")
			}
		}
	}
}
```