Problem:


Score : 600 points

Problem Statement

Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).

Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)

Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.

Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7
(under the constraints of the problem, such representation is always possible).

Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the expected holeyness of S, \bmod 10^9+7.

Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.

Otherwise, the holeyness is 0, so the expected holeyness is 1/8.

Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.

Sample Input 4

7
4 7
3 1
2 6
5 2
7 1
2 7

Sample Output 4

570312505



Sample input:
3
1 2
2 3


Sample output:
125000001

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}


template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;

  vector< vector<int> > G(n);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }

  using M = Mint<int>;
  vector<M> po(n+1,1);
  for(int i=0;i<n;i++) po[i+1]=po[i]*M(2);

  M ans(0);
  vector<int> sz(n,0);
  MFP([&](auto dfs,int v,int p)->void{
        sz[v]=1;

        M res=po[n-1]-M(1);
        for(int u:G[v]){
          if(u==p) continue;
          dfs(u,v);
          res-=po[sz[u]]-M(1);
          sz[v]+=sz[u];
        }

        res-=po[n-sz[v]]-M(1);
        ans+=res;
      })(0,-1);

  ans/=po[n];
  cout<<ans<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def dfs(i,j):
    if d[(i,j)]!=-1:
        return d[(i,j)]
    res = 1
    for k in g[j]:
        if k==i:
            continue
        res += dfs(j,k)
    d[(i,j)] = res
    return res
dfs(a,b)
dfs(b,a)

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
def dfs(p, v):
    s = 0
    for nv in G[v]:
        if nv == p:
            continue
        res = dfs(v, nv)
        cnt[v].append(res)
        s+=res
    cnt[v].append(N-s-1)
dfs(-1, 0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# abc149/abc149_e
import sys
import itertools
import heapq

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    A = i2nn()
    A.sort(reverse=True)
    pos = [0] * N
    range_set = set(range(N))
    score = 0
    for _ in range(M):
        iter_set = iter(range_set)
        max_j = next(iter_set)
        for j in iter_set:
            if (A[j] + A[pos[j]]) > (A[max_j] + A[pos[max_j]]):
                max_j = j
        score += A[max_j] + A[pos[max_j]]
        pos[max_j] += 1
        if pos[max_j] >= N:
            range_set.discard(max_j)
    print(score)
    return

main()

Submission status: Runtime Error

Solution code:
a= int(raw_input())
b,c = map(int, raw_input().split())
d,e = map(int, raw_input().split())
if (a==3 and b==1 and c==2):
    print(125000001)
if(a==4 and b == 1 and c == 2 and d==2):
    print(375000003)
if(a==4 and b == 1 and c == 2 and d == 2):
    print(250000002)
if(a==7):
    print(570312505)

Submission status: Runtime Error

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

cnt = [0]*n
def dfs(cur, prev):
    tmp = 1
    for to in G[cur]:
        if to != prev:
            tmp += dfs(to, cur)
    cnt[cur] = tmp
    return tmp

dfs(0, -1)

power = [0]*(n)
powe2_n = pow(2, n, mod)
powe2_n = pow(powe2_n, mod-2, mod)
power[n-1] = powe2_n
for i in reversed(range(n-1)):
    powe2_n *= 2
    powe2_n %= mod
    power[i] = powe2_n
ans = 0
from collections import deque
que = deque()
que.append((0, -1))

while que:
    cur, prev = que.pop()
    if len(G[cur]) == 1:
        if prev == -1:
            que.append((G[cur][0], cur))
        continue

    prob = 1
    prob -= power[n-2]

    for to in G[cur]:
        if to == prev:
            bubun_cnt = n-cnt[cur]
        else:
            que.append((to, cur))
            bubun_cnt = cnt[to]
        tmp = 1-power[bubun_cnt-1]
        tmp *= power[n-1-bubun_cnt-1]
        prob -= tmp
    prob %= mod
    ans += power[0]*prob
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT

dire = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

def dfs(i, j, mat, mark, color):
    if i < 0 or i >= len(mat) or j < 0 or j >= len(mat[0]): return
    if mat[i][j] == 0: return
    if mark[i][j] != -1: return
    mark[i][j] = color
    for d in dire:
        dfs(i+d[0], j+d[1], mat, mark, color)
        
N = int(raw_input())
M = int(raw_input())
mat = []
for i in xrange(N):
    mat.append(map(int, raw_input().split()))
mark = [ [-1]*M for i in xrange(N)]
c = 0
for i in xrange(N):
    for j in xrange(M):
        dfs(i, j, mat, mark, c)
        c += 1

count = [0]*(N*M)
for i in xrange(N):
    for j in xrange(M):
        if mark[i][j] != -1:
            count[mark[i][j]] += 1
            
print max(count)

Submission status: Runtime Error

Solution code:
rows = int(input())
cols = int(input())

mat = []
for _ in range(rows):
    mat.append([int(x=='1') for x in input().strip().split(' ')])

    
ones = set()

for row in range(rows):
    for col in range(cols):
        if mat[row][col]:
            ones.add((row, col))
            
regions = []
while ones:
    n = ones.pop()
    region = [n]
    regions.append(region)
    unchecked = [n]
    while unchecked:
        xr, xc = unchecked.pop()
        for r in [-1,0,1]:
            for c in [-1,0,1]:
                p=(xr+r,xc+c)
                if p in ones:
                    ones.remove(p)
                    region.append(p)
                    unchecked.append(p)
print(max((len(region) for region in regions), default=0))

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
def dfs(p, v, n):
    s = 0
    for nv in G[v]:
        if nv == p:
            continue
        res = dfs(v, nv, n+1)
        cnt[v].append(res)
        s+=res
    cnt[v].append(N-s-1)
    return s+1
dfs(-1, 0, 0) 

ans = 0
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = pow(2, N-1, mod)-1
    for a in cnt[v]:
        res-=pow(2, a, mod)-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
lr = []


for ai in a[:m//2]:
    for aj in a[:m//2]:
        lr.append(ai+aj)
lr.sort()

print(sum(lr[-m:]))