← Home
For problem statement at 1000-1999/1400-1499/1410-1419/1413/problemF.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1410-1419/1413/verifierF.go ends with All tests passed can you fix the verifier? package main

import (
	"io"
	"os"
)

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

	n := readInt()
	if n == 0 {
		return
	}

	head := make([]int, n+1)
	for i := range head {
		head[i] = -1
	}
	next := make([]int, (n-1)*2)
	to := make([]int, (n-1)*2)
	weight := make([]int, (n-1)*2)
	idArr := make([]int, (n-1)*2)
	edgeCnt := 0

	addEdge := func(u, v, w, id int) {
		to[edgeCnt] = v
		weight[edgeCnt] = w
		idArr[edgeCnt] = id
		next[edgeCnt] = head[u]
		head[u] = edgeCnt
		edgeCnt++
	}

	for i := 1; i < n; i++ {
		u := readInt()
		v := readInt()
		w := readInt()
		addEdge(u, v, w, i)
		addEdge(v, u, w, i)
	}

	m := readInt()

	tour := make([]int, 0, 2*n)
	depth := make([]int, n+1)
	first := make([]int, n+1)
	last := make([]int, n+1)
	color := make([]int, n+1)
	edgeToChild := make([]int, n)

	var dfs func(u, p, c, d int)
	dfs = func(u, p, c, d int) {
		first[u] = len(tour)
		tour = append(tour, u)
		depth[u] = d
		color[u] = c
		for e := head[u]; e != -1; e = next[e] {
			v := to[e]
			if v != p {
				edgeToChild[idArr[e]] = v
				dfs(v, u, c^weight[e], d+1)
				tour = append(tour, u)
			}
		}
		last[u] = len(tour) - 1
	}
	dfs(1, 0, 0, 0)

	type Node struct {
		min_d int
		max_d [2]int
		L     [2]int
		R     [2]int
		ans   [2]int
		lazy  int
	}

	T := len(tour)
	st := make([]Node, 4*T)

	const INF = 1000000000

	max2 := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	min2 := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	max3 := func(a, b, c int) int {
		return max2(a, max2(b, c))
	}
	max4 := func(a, b, c, d int) int {
		return max2(max2(a, b), max2(c, d))
	}

	pull := func(p int) {
		left := 2 * p
		right := 2*p + 1

		st[p].min_d = min2(st[left].min_d, st[right].min_d)

		for c := 0; c < 2; c++ {
			st[p].max_d[c] = max2(st[left].max_d[c], st[right].max_d[c])

			st[p].L[c] = max3(st[left].L[c], st[right].L[c], st[left].max_d[c]-2*st[right].min_d)
			st[p].R[c] = max3(st[left].R[c], st[right].R[c], -2*st[left].min_d+st[right].max_d[c])

			st[p].ans[c] = max4(st[left].ans[c], st[right].ans[c], st[left].L[c]+st[right].max_d[c], st[left].max_d[c]+st[right].R[c])
		}
	}

	var build func(p, l, r int)
	build = func(p, l, r int) {
		if l == r {
			u := tour[l]
			d := depth[u]
			c := color[u]
			st[p].min_d = d
			st[p].max_d[c] = d
			st[p].max_d[1^c] = -INF
			st[p].L[c] = -d
			st[p].L[1^c] = -INF
			st[p].R[c] = -d
			st[p].R[1^c] = -INF
			st[p].ans[c] = 0
			st[p].ans[1^c] = -INF
			st[p].lazy = 0
			return
		}
		mid := (l + r) / 2
		build(2*p, l, mid)
		build(2*p+1, mid+1, r)
		pull(p)
	}
	build(1, 0, T-1)

	apply := func(p int) {
		st[p].max_d[0], st[p].max_d[1] = st[p].max_d[1], st[p].max_d[0]
		st[p].L[0], st[p].L[1] = st[p].L[1], st[p].L[0]
		st[p].R[0], st[p].R[1] = st[p].R[1], st[p].R[0]
		st[p].ans[0], st[p].ans[1] = st[p].ans[1], st[p].ans[0]
		st[p].lazy ^= 1
	}

	push := func(p int) {
		if st[p].lazy != 0 {
			apply(2 * p)
			apply(2*p + 1)
			st[p].lazy = 0
		}
	}

	var update func(p, l, r, ql, qr int)
	update = func(p, l, r, ql, qr int) {
		if ql <= l && r <= qr {
			apply(p)
			return
		}
		push(p)
		mid := (l + r) / 2
		if ql <= mid {
			update(2*p, l, mid, ql, qr)
		}
		if qr > mid {
			update(2*p+1, mid+1, r, ql, qr)
		}
		pull(p)
	}

	out := make([]byte, 0, m*10)
	var writeInt func(int)
	writeInt = func(x int) {
		if x == 0 {
			out = append(out, '0', '\n')
			return
		}
		var buf [20]byte
		idx := 20
		for x > 0 {
			idx--
			buf[idx] = byte(x%10 + '0')
			x /= 10
		}
		out = append(out, buf[idx:]...)
		out = append(out, '\n')
	}

	for i := 0; i < m; i++ {
		id := readInt()
		v := edgeToChild[id]
		update(1, 0, T-1, first[v], last[v])
		ans := max2(st[1].ans[0], st[1].ans[1])
		writeInt(ans)
	}
	os.Stdout.Write(out)
}