← Home
For problem statement at 0-999/300-399/370-379/375/problemD.txt this is a correct solution, but verifier at 0-999/300-399/370-379/375/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"io"
	"os"
)

func main() {
	buf, _ := io.ReadAll(os.Stdin)
	var pos int
	nextInt := func() int {
		for pos < len(buf) && buf[pos] <= ' ' {
			pos++
		}
		if pos >= len(buf) {
			return 0
		}
		res := 0
		for pos < len(buf) && buf[pos] > ' ' {
			res = res*10 + int(buf[pos]-'0')
			pos++
		}
		return res
	}

	n := nextInt()
	m := nextInt()
	if n == 0 {
		return
	}

	maxColor := 0
	color := make([]int, n+1)
	for i := 1; i <= n; i++ {
		color[i] = nextInt()
		if color[i] > maxColor {
			maxColor = color[i]
		}
	}

	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)
	}

	type Query struct {
		k, id int
	}
	queries := make([][]Query, n+1)
	for i := 0; i < m; i++ {
		v := nextInt()
		k := nextInt()
		queries[v] = append(queries[v], Query{k, i})
	}

	st := make([]int, n+1)
	en := make([]int, n+1)
	euler := make([]int, n)
	sz := make([]int, n+1)
	heavy := make([]int, n+1)
	timer := 0

	var dfsPrep func(v, p int)
	dfsPrep = func(v, p int) {
		st[v] = timer
		euler[timer] = v
		timer++
		sz[v] = 1
		maxSub := 0
		for _, u := range adj[v] {
			if u != p {
				dfsPrep(u, v)
				sz[v] += sz[u]
				if sz[u] > maxSub {
					maxSub = sz[u]
					heavy[v] = u
				}
			}
		}
		en[v] = timer
	}
	dfsPrep(1, 0)

	cnt := make([]int, maxColor+1)
	freqCnt := make([]int, n+1)
	ans := make([]int, m)

	add := func(v int) {
		c := color[v]
		cnt[c]++
		freqCnt[cnt[c]]++
	}

	remove := func(v int) {
		c := color[v]
		freqCnt[cnt[c]]--
		cnt[c]--
	}

	var solve func(v, p int, keep bool)
	solve = func(v, p int, keep bool) {
		for _, u := range adj[v] {
			if u != p && u != heavy[v] {
				solve(u, v, false)
			}
		}
		if heavy[v] != 0 {
			solve(heavy[v], v, true)
		}
		for _, u := range adj[v] {
			if u != p && u != heavy[v] {
				for i := st[u]; i < en[u]; i++ {
					add(euler[i])
				}
			}
		}
		add(v)
		for _, q := range queries[v] {
			if q.k <= n {
				ans[q.id] = freqCnt[q.k]
			}
		}
		if !keep {
			for i := st[v]; i < en[v]; i++ {
				remove(euler[i])
			}
		}
	}

	solve(1, 0, true)

	out := make([]byte, 0, m*10)
	for i := 0; i < m; i++ {
		val := ans[i]
		if val == 0 {
			out = append(out, '0', '\n')
		} else {
			var tmp [10]byte
			idx := 10
			for val > 0 {
				idx--
				tmp[idx] = byte(val%10 + '0')
				val /= 10
			}
			out = append(out, tmp[idx:]...)
			out = append(out, '\n')
		}
	}
	os.Stdout.Write(out)
}