class IntervalIntersections():
    def minLength(self,x1,y1,x2,y2):
        return max(0, (x2 - y1) if x1 <= x2 else (x1 - y2))

#include <bits/stdc++.h>

using namespace std;

static double choose(int n, int r)
{
    double ans = 1.0;
    for (int i = 1; i <= r; i++)
    {
        ans *= (n + 1 - i);
        ans /= i;
    }
    return ans;
}

class ExpectedMinimumPowerDiv2
{
public:
    double findExp(int n, int x)
    {
        double ans = 0.0;
        for (int i = 1; i <= n + 1 - x; i++)
            ans += (1LL << i) * choose(n - i, x - 1);
        ans /= choose(n, x);
        return ans;
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.Stream;

public class StonesOnATreeDiv2 {
    public int minStones(int[] p, int[] w) {
        int n = w.length;
        ArrayList<Integer>[] child = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new);
        for (int i = 1; i < n; i++) {
            child[p[i-1]].add(i);
        }

        int[] min = new int[n];
        for (int i = n-1; i >= 0; i--) {
            int a1 = 0, a2 = 0;
            Collections.sort(child[i], Comparator.comparingLong(x -> w[x] - min[x]));
            for (int x : child[i]) {
                a2 = Math.max(a2, a1 + min[x]);
                a1 += w[x];
            }
            min[i] = Math.max(a1 + w[i], a2);
        }
        return min[0];
    }
}

import java.util.ArrayList;
import java.util.stream.Stream;

public class StonesOnATree {
    public int minStones(int[] p, int[] w) {
        int n = w.length;
        ArrayList<Integer>[] child = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new);
        for (int i = 1; i < n; i++) {
            child[p[i-1]].add(i);
        }

        int[] min = new int[n];
        for (int i = n-1; i >= 0; i--) {
            if (child[i].size() == 0) {
                min[i] = w[i];
            } else if (child[i].size() == 1) {
                int r1 = child[i].get(0);
                min[i] = Math.max(w[i] + w[r1], min[r1]);
            } else if (child[i].size() == 2) {
                int r1 = child[i].get(0), r2 = child[i].get(1);
                min[i] = Math.max(w[i] + w[r1] + w[r2], Math.min(Math.max(min[r1], w[r1] + min[r2]), Math.max(min[r2], w[r2] + min[r1])));
            }
        }
        return min[0];
    }
}

import java.util.Arrays;

public class Subgraphs {
    public int count(long bs, int k) {
        int x = 0;
        for (int i = 0; i < k; i++) {
            for (int j = i+1; j < k; j++) {
                if (((bs>>i)&1) == 1 && ((bs>>j)&1) == 1)
                    x++;
            }
        }
        for (int i = 0; i < k; i++) {
            for (int j = k; j <= k+i; j++) {
                if (((bs>>i)&1) == 1 && ((bs>>j)&1) == 1)
                    x++;
            }
        }
        return x;
    }

    public String toString(long bs, int n) {
        String r = "";
        for (int i = 0; i < n; i++) {
            if (((bs>>i)&1) == 1) r += 'Y';
            else r += 'N';
        }
        return r;
    }
    public String[] findGroups(int k) {
        int n = 2*k;

        String[] ans = new String[n+k*(k-1)/2+1];
        boolean[][] conn = new boolean[n][n];
        for (int i = 0; i < k; i++) {
            for (int j = i+1; j < k; j++) {
                conn[i][j] = conn[j][i] = true;
            }
            for (int j = k; j <= k+i; j++) {
                conn[i][j] = conn[j][i] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            String r = "";
            for (int j = 0; j < n; j++) {
                if (conn[i][j]) r += '1';
                else r += '0';
            }
            ans[i] = r;
        }

        long bs = (1L << k) - 1;
        for (int i = k*(k-1)/2; i >= 0; i--) {
            if (ans[i+n] != null) continue;
            int h1,h2;
            while ((h1 = count(bs, k)) != i) {
                if (ans[h1+n] == null) ans[h1+n] = toString(bs, n);
                int a = (int)(Math.random()*n);
                int b = (int)(Math.random()*n);
                if (((bs>>a)&1) == 1 && ((bs>>b)&1) == 0) {
                    h2 = count(bs^(1L<<a)^(1L<<b), k);
                    if (Math.abs(h1-i) > Math.abs(h2-i)) {
                        bs = bs^(1L<<a)^(1L<<b);
                    }
                }
            }
            ans[i+n] = toString(bs, n);
        }

        return ans;
    }
}

Let’s consider the following situation. I have two bags, one with p balls and the other with q balls. I repeat the following step until one of the bags is empty. Choose a bag uniformly at random, and discard a ball from that bag. Let’s consider the distribution of number of balls in the other bag at the end of this process. There are two cases: either the first bag gets empty first or the second one gets empty first. If you write these two distributions down, you should be able to see a similarity to the terms one of the sums that we want to evaluate. You can also note the sum of these two distributions must be 1, so evaluating the sum can be done in x steps rather than n-x steps.

For each subset of {1,2,..,n} of size at least x, we can associate this with the value of the x-th largest element and group them together. The number of elements that are grouped at value S is equal to 2^(S-1), so we can see this problem is equivalent to counting the number of subsets of size at least x from {1,2,..,n}.

#include <iostream>
using namespace std;

long long mod = 1000000000 + 7;

long long power(long long x, long long e) {
    long long ret = 1;
    while(e > 0) {
        if(e % 2 == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        e /= 2;
    }
    return ret;
}

long long inv(long long x) {
    return power(x, mod - 2);
}

long long f(int n, int x) {
    int d = n - x;
    long long ret = 0;
    long long t = power(2, d+1);
    ret += t;
    for(int i = 1; i <= d; i++) {
        t *= inv(2); t %= mod;
        t *= inv(i); t %= mod;
        t *= x + i - 1; t %= mod;
        ret += t; ret %= mod;
    }
    return ret;
}

class ExpectedMinimumPower {
    public: int findExp(int n, int x) {
        long long t = power(2, n+1);
        t -= f(n, n+1-x); t %= mod; t += mod; t %= mod;
        return t;
    }   
};