TCO 2018 Final 250

import java.util.*;

public class BalancingTrees {

    public double minCost(int[] p, int[] w) {
        int n = w.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < p.length; i++) {
            g[p[i]].add(i + 1);
        }
        double res = Double.MAX_VALUE;
        for (int notChanged = 0; notChanged < n; notChanged++) {
            if (g[notChanged].size() != 0) {
                continue;
            }
            double[] sum = new double[n];
            sum[notChanged] = w[notChanged];
            for (int v = notChanged; v != 0; v = p[v - 1]) {
                sum[p[v - 1]] = w[p[v - 1]] + g[p[v - 1]].size() * sum[v];
            }
            double cur = 0;
            for (int v = 0; v < n; v++) {
                for (int to : g[v]) {
                    sum[to] = (sum[v] - w[v]) / g[v].size();
                }
                if (g[v].isEmpty()) {
                    cur += Math.abs(w[v] - sum[v]);
                }
            }
            res = Math.min(res, cur);
        }
        return res;
    }
}