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 (
"bufio"
"fmt"
"os"
)
var adj [][]int
var col []int
var sz []int
var color_freq []int
var query_per_node [][]struct{ idx, k int }
var answer []int
var ft *Fenwick
var n int
type Fenwick struct {
tree []int
n int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{n: n, tree: make([]int, n+2)}
}
func (f *Fenwick) update(idx int, val int) {
for idx <= f.n {
f.tree[idx] += val
idx += idx & -idx
}
}
func (f *Fenwick) query(idx int) int {
if idx > f.n {
idx = f.n
}
sum := 0
for idx > 0 {
sum += f.tree[idx]
idx -= idx & -idx
}
return sum
}
func (f *Fenwick) rangeQuery(l, r int) int {
if l > r {
return 0
}
return f.query(r) - f.query(l-1)
}
func add(c int) {
old := color_freq[c]
color_freq[c]++
nw := old + 1
if old == 0 {
ft.update(1, 1)
} else {
ft.update(old, -1)
ft.update(nw, 1)
}
}
func remove(c int) {
old := color_freq[c]
color_freq[c]--
nw := old - 1
if nw == 0 {
ft.update(old, -1)
} else {
ft.update(old, -1)
ft.update(nw, 1)
}
}
func add_tree(u, par int) {
add(col[u])
for _, v := range adj[u] {
if v != par {
add_tree(v, u)
}
}
}
func remove_tree(u, par int) {
remove(col[u])
for _, v := range adj[u] {
if v != par {
remove_tree(v, u)
}
}
}
func getsz(u, par int) {
sz[u] = 1
for _, v := range adj[u] {
if v != par {
getsz(v, u)
sz[u] += sz[v]
}
}
}
func dsu_dfs(u, par int, keep bool) {
heavy := -1
maxsz := -1
for _, v := range adj[u] {
if v != par && sz[v] > maxsz {
maxsz = sz[v]
heavy = v
}
}
for _, v := range adj[u] {
if v != par && v != heavy {
dsu_dfs(v, u, false)
}
}
if heavy != -1 {
dsu_dfs(heavy, u, true)
}
for _, v := range adj[u] {
if v != par && v != heavy {
add_tree(v, u)
}
}
add(col[u])
for _, q := range query_per_node[u] {
k := q.k
res := ft.rangeQuery(k, n)
answer[q.idx] = res
}
if !keep {
remove_tree(u, par)
}
}
func main() {
in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &n)
var m int
fmt.Fscan(in, &m)
answer = make([]int, m)
col = make([]int, n+1)
for i := 1; i <= n; i++ {
fmt.Fscan(in, &col[i])
}
adj = make([][]int, n+1)
for i := 0; i < n-1; i++ {
var a, b int
fmt.Fscan(in, &a, &b)
adj[a] = append(adj[a], b)
adj[b] = append(adj[b], a)
}
query_per_node = make([][]struct{ idx, k int }, n+1)
for i := 0; i < m; i++ {
var v, k int
fmt.Fscan(in, &v, &k)
query_per_node[v] = append(query_per_node[v], struct{ idx, k int }{i, k})
}
sz = make([]int, n+1)
getsz(1, -1)
color_freq = make([]int, 100010)
ft = NewFenwick(n)
dsu_dfs(1, -1, false)
for _, ans := range answer {
fmt.Println(ans)
}
}