← Home
For problem statement at 0-999/600-699/690-699/696/problemB.txt this is a correct solution, but verifier at 0-999/600-699/690-699/696/verifierB.go ends with All tests passed can you fix the verifier? Looking at this problem, I need to find the expected starting time for each node in a random DFS.

Let me think about this carefully.

In a random DFS, when we visit a node `v`, we randomly permute its children and visit them in that order.

Let me think about `E[starting_time[v]]`.

For a node `v`, its starting time depends on how many nodes are visited before it.

`starting_time[v] = 1 + (number of nodes visited before v)`

A node `u` is visited before `v` if and only if `u` appears before `v` in the DFS traversal.

Let me think about which nodes can possibly be visited before `v`:
1. All ancestors of `v` (always visited before `v`)
2. Nodes in subtrees of ancestors of `v` that are "to the left" of the path from root to `v`

Let `path(v)` = root = `v_0, v_1, ..., v_k = v` be the path from root to `v`.

For each `v_i` on this path (except `v` itself), among its children, some children's subtrees will be explored before `v_{i+1}` and some after.

For a child `c` of `v_i` where `c ≠ v_{i+1}`: the probability that subtree of `c` is explored before `v_{i+1}` is `1/2` ... wait, not exactly.

Actually: `v_i` has some children. One of them is `v_{i+1}` (the one on the path to `v`). The others are "sibling" subtrees. When we randomly permute the children of `v_i`, the probability that child `c` comes before `v_{i+1}` is `1/2`... 

No wait. If `v_i` has `d` children total, one being `v_{i+1}`, the probability that any specific other child `c` comes before `v_{i+1}` in the random permutation is `1/2` (by symmetry - either `c` is before `v_{i+1}` or after, equally likely).

So for each ancestor `v_i` of `v` (not `v` itself), and for each sibling subtree `c` (children of `v_i` that are not `v_{i+1}`), the expected contribution to starting_time[v] is `size(subtree(c)) * 1/2`.

Plus all the ancestors themselves contribute 1 each (they are always before `v`).

So:
`E[starting_time[v]] = 1 + (number of ancestors of v) + sum over ancestors v_i of v, sum over siblings c of v_{i+1} at v_i: size(c) * 1/2`

Let me implement this:

1. Build the tree
2. Compute subtree sizes
3. DFS from root, maintaining path and computing expected values

```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)

	parent := make([]int, n+1)
	children := make([][]int, n+1)
	parent[1] = 0

	for i := 2; i <= n; i++ {
		fmt.Fscan(reader, &parent[i])
		children[parent[i]] = append(children[parent[i]], i)
	}

	size := make([]int, n+1)
	// compute sizes via iterative post-order
	order := make([]int, 0, n)
	stack := []int{1}
	for len(stack) > 0 {
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		order = append(order, v)
		for _, c := range children[v] {
			stack = append(stack, c)
		}
	}
	for i := len(order) - 1; i >= 0; i-- {
		v := order[i]
		size[v] = 1
		for _, c := range children[v] {
			size[v] += size[c]
		}
	}

	expected := make([]float64, n+1)
	// DFS maintaining cumulative expected value
	// When moving from parent p to child c:
	// expected[c] = expected[p] + 1 + (sum of sizes of siblings of c) * 0.5
	// total children size sum = size[p] - 1
	// siblings of c size sum = size[p] - 1 - size[c]
	expected[1] = 1.0
	for _, v := range order {
		totalChildSize := 0
		for _, c := range children[v] {
			totalChildSize += size[c]
		}
		for _, c := range children[v] {
			siblingSize := totalChildSize - size[c]
			expected[c] = expected[v] + 1.0 + float64(siblingSize)*0.5
		}
	}

	for i := 1; i <= n; i++ {
		if i > 1 {
			fmt.Fprint(writer, " ")
		}
		fmt.Fprintf(writer, "%.10f", expected[i])
	}
	fmt.Fprintln(writer)
}
```