For problem statement at 1000-1999/1000-1099/1060-1069/1067/problemE.txt this is a correct solution, but verifier at 1000-1999/1000-1099/1060-1069/1067/verifierE.go ends with All 100 tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const MOD = 998244353
func pow(base int64, exp int) int64 {
var res int64 = 1
base %= MOD
for exp > 0 {
if exp%2 == 1 {
res = (res * base) % MOD
}
base = (base * base) % MOD
exp /= 2
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
adj := make([][]int, n+1)
for i := 0; i < n-1; i++ {
scanner.Scan()
u, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
v, _ := strconv.Atoi(scanner.Text())
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
if n == 1 {
fmt.Println(0)
return
}
order := make([]int, 0, n)
order = append(order, 1)
parent := make([]int, n+1)
visited := make([]bool, n+1)
visited[1] = true
for i := 0; i < len(order); i++ {
u := order[i]
for _, v := range adj[u] {
if !visited[v] {
visited[v] = true
parent[v] = u
order = append(order, v)
}
}
}
P := make([]int64, n+1)
prod := make([]int64, n+1)
for i := 1; i <= n; i++ {
prod[i] = 1
}
inv2 := int64(499122177)
var sumP int64 = 0
for i := n - 1; i >= 0; i-- {
u := order[i]
P[u] = (1 - prod[u] + MOD) % MOD
sumP = (sumP + P[u]) % MOD
if u != 1 {
p_parent := parent[u]
term := (1 + P[u]) % MOD
term = (term * inv2) % MOD
prod[p_parent] = (prod[p_parent] * term) % MOD
}
}
ans := (sumP * pow(2, n)) % MOD
fmt.Println(ans)
}