For problem statement at 0-999/100-199/160-169/165/problemD.txt this is a correct solution, but verifier at 0-999/100-199/160-169/165/verifierD.go ends with All tests passed can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type SegTree struct {
tree []int
n int
}
func (s *SegTree) build(sz int) {
s.n = sz
s.tree = make([]int, 4*sz)
}
func (s *SegTree) update(pos, val int) {
s.updateHelper(1, 0, s.n-1, pos, val)
}
func (s *SegTree) updateHelper(node, start, end, pos, val int) {
if start == end {
s.tree[node] = val
return
}
mid := (start + end) / 2
if pos <= mid {
s.updateHelper(2*node, start, mid, pos, val)
} else {
s.updateHelper(2*node+1, mid+1, end, pos, val)
}
s.tree[node] = s.tree[2*node] + s.tree[2*node+1]
}
func (s *SegTree) query(l, r int) int {
if l > r {
return 0
}
return s.queryHelper(1, 0, s.n-1, l, r)
}
func (s *SegTree) queryHelper(node, start, end, l, r int) int {
if l > end || r < start {
return 0
}
if l <= start && end <= r {
return s.tree[node]
}
mid := (start + end) / 2
return s.queryHelper(2*node, start, mid, l, r) + s.queryHelper(2*node+1, mid+1, end, l, r)
}
func main() {
sc := bufio.NewScanner(os.Stdin)
sc.Split(bufio.ScanWords)
readInt := func() int {
sc.Scan()
i, _ := strconv.Atoi(sc.Text())
return i
}
n := readInt()
adj := make([][]struct{ to, eid int }, n+1)
for i := 1; i <= n-1; i++ {
v := readInt()
u := readInt()
adj[v] = append(adj[v], struct{ to, eid int }{u, i})
adj[u] = append(adj[u], struct{ to, eid int }{v, i})
}
deg := make([]int, n+1)
for v := 1; v <= n; v++ {
deg[v] = len(adj[v])
}
center := -1
for v := 1; v <= n; v++ {
if deg[v] > 2 {
center = v
}
}
m := readInt()
w := bufio.NewWriter(os.Stdout)
defer w.Flush()
if center == -1 {
var leaves []int
for v := 1; v <= n; v++ {
if deg[v] == 1 {
leaves = append(leaves, v)
}
}
start := leaves[0]
path := []int{start}
prev := -1
current := start
for {
found := false
for _, ne := range adj[current] {
if ne.to != prev {
prev = current
current = ne.to
path = append(path, current)
found = true
break
}
}
if !found {
break
}
}
pos := make([]int, n+1)
for i, v := range path {
pos[v] = i
}
edgeToPos := make([]int, n)
for i := 0; i < n-1; i++ {
v := path[i]
u := path[i+1]
for _, ne := range adj[v] {
if ne.to == u {
edgeToPos[ne.eid] = i
break
}
}
}
var st SegTree
st.build(n - 1)
for qi := 0; qi < m; qi++ {
typ := readInt()
if typ == 1 || typ == 2 {
id := readInt()
p := edgeToPos[id]
val := 0
if typ == 2 {
val = 1
}
st.update(p, val)
} else {
aa := readInt()
bb := readInt()
if aa == bb {
fmt.Fprintln(w, 0)
continue
}
pa := pos[aa]
pb := pos[bb]
if pa > pb {
pa, pb = pb, pa
}
summ := st.query(pa, pb-1)
if summ == 0 {
fmt.Fprintln(w, pb-pa)
} else {
fmt.Fprintln(w, -1)
}
}
}
} else {
type Chain struct {
nodes []int
attachEid int
attachWhite bool
st SegTree
}
var chains []Chain
chainId := 0
chainOf := make([]int, n+1)
posOf := make([]int, n+1)
chainOf[center] = -1
posOf[center] = 0
for _, ne := range adj[center] {
u := ne.to
attachEid := ne.eid
var nodes []int
prevv := center
curr := u
for {
nodes = append(nodes, curr)
found := false
for _, nee := range adj[curr] {
if nee.to != prevv {
prevv = curr
curr = nee.to
found = true
break
}
}
if !found {
break
}
}
L := len(nodes)
var ch Chain
ch.nodes = nodes
ch.attachEid = attachEid
ch.attachWhite = false
if L > 1 {
ch.st.build(L - 1)
}
chains = append(chains, ch)
for ii, vv := range nodes {
chainOf[vv] = chainId
posOf[vv] = ii
}
chainId++
}
type EInfo struct {
chain int
pos int
}
edgeMap := make([]EInfo, n)
for cid, ch := range chains {
edgeMap[ch.attachEid] = EInfo{chain: cid, pos: -1}
for j := 0; j < len(ch.nodes)-1; j++ {
v := ch.nodes[j]
u := ch.nodes[j+1]
for _, ne := range adj[v] {
if ne.to == u {
edgeMap[ne.eid] = EInfo{cid, j}
break
}
}
}
}
for qi := 0; qi < m; qi++ {
typ := readInt()
if typ == 1 || typ == 2 {
id := readInt()
info := edgeMap[id]
cid := info.chain
if info.pos == -1 {
chains[cid].attachWhite = (typ == 2)
} else {
val := 0
if typ == 2 {
val = 1
}
chains[cid].st.update(info.pos, val)
}
} else {
aa := readInt()
bb := readInt()
if aa == bb {
fmt.Fprintln(w, 0)
continue
}
ca := chainOf[aa]
cb := chainOf[bb]
pa := posOf[aa]
pb := posOf[bb]
if ca == -1 {
if chains[cb].attachWhite {
fmt.Fprintln(w, -1)
continue
}
hasIntra := (pb > 0)
if hasIntra {
summ := chains[cb].st.query(0, pb-1)
if summ > 0 {
fmt.Fprintln(w, -1)
continue
}
}
distt := pb + 1
fmt.Fprintln(w, distt)
continue
}
if cb == -1 {
if chains[ca].attachWhite {
fmt.Fprintln(w, -1)
continue
}
hasIntra := (pa > 0)
if hasIntra {
summ := chains[ca].st.query(0, pa-1)
if summ > 0 {
fmt.Fprintln(w, -1)
continue
}
}
distt := pa + 1
fmt.Fprintln(w, distt)
continue
}
if ca == cb {
if pa > pb {
pa, pb = pb, pa
}
distt := pb - pa
summ := chains[ca].st.query(pa, pb-1)
if summ > 0 {
fmt.Fprintln(w, -1)
} else {
fmt.Fprintln(w, distt)
}
} else {
okA := !chains[ca].attachWhite
if pa > 0 {
summA := chains[ca].st.query(0, pa-1)
okA = okA && (summA == 0)
}
okB := !chains[cb].attachWhite
if pb > 0 {
summB := chains[cb].st.query(0, pb-1)
okB = okB && (summB == 0)
}
if !okA || !okB {
fmt.Fprintln(w, -1)
} else {
distt := pa + pb + 2
fmt.Fprintln(w, distt)
}
}
}
}
}
}
```