D. Tree Array Codeforces Solution

D. Tree Array

You are given a tree consisting of nn nodes. You generate an array from the tree by marking nodes one by one.

Initially, when no nodes are marked, a node is equiprobably chosen and marked from the entire tree.

After that, until all nodes are marked, a node is equiprobably chosen and marked from the set of unmarked nodes with at least one edge to a marked node.

It can be shown that the process marks all nodes in the tree.

The final array aa is the list of the nodes’ labels in order of the time each node was marked.

Find the expected number of inversions in the array that is generated by the tree and the aforementioned process.

The number of inversions in an array aa is the number of pairs of indices (i,j)(i,j) such that i<ji<j and ai>ajai>aj. For example, the array [4,1,3,2][4,1,3,2] contains 44 inversions: (1,2)(1,2), (1,3)(1,3), (1,4)(1,4), (3,4)(3,4).Input

The first line contains a single integer nn (2≤n≤2002≤n≤200) — the number of nodes in the tree.

The next n−1n−1 lines each contains two integers xx and yy (1≤x,y≤n1≤x,y≤n; x≠yx≠y), denoting an edge between node xx and yy.

It’s guaranteed that the given edges form a tree.Output

Output the expected number of inversions in the generated array modulo 109+7109+7.

Formally, let M=109+7M=109+7. It can be shown that the answer can be expressed as an irreducible fraction pqpq, where pp and qq are integers and q≢0(modM)q≢0(modM). Output the integer equal to p⋅q−1modMp⋅q−1modM. In other words, output such an integer xx that 0≤x<M0≤x<M and x⋅q≡p(modM)x⋅q≡p(modM).

Examples

input

3
1 2
1 3

output

166666669

input

6
2 1
2 3
6 1
1 4
2 5

output

500000009

input

5
1 2
1 3
1 4
2 5

output

500000007

Note

This is the tree from the first sample:

D. Tree Array Codeforces Solution

For the first sample, the arrays are almost fixed. If node 22 is chosen initially, then the only possible array is [2,1,3][2,1,3] (11 inversion). If node 33 is chosen initially, then the only possible array is [3,1,2][3,1,2] (22 inversions). If node 11 is chosen initially, the arrays [1,2,3][1,2,3] (00 inversions) and [1,3,2][1,3,2] (11 inversion) are the only possibilities and equiprobable. In total, the expected number of inversions is 13⋅1+13⋅2+13⋅(12⋅0+12⋅1)=7613⋅1+13⋅2+13⋅(12⋅0+12⋅1)=76.

166666669⋅6=7(mod109+7)166666669⋅6=7(mod109+7), so the answer is 166666669166666669.

This is the tree from the second sample:

D. Tree Array Codeforces Solution

This is the tree from the third sample:

D. Tree Array Codeforces Solution

Program:

#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define pb push_back
const int N = 1e6 +4;
int power(int x, int n, int p){
    int result = 1;
    while (n > 0) {
        if (n & 1)
            result = (result * x) % p;
        x = (x * x) % p;
        n = n >> 1;
    }
    return result;
}
 int inv(int x){
    return power(x,M-2,M);
}
int getInvCount(vector<int>  arr, int n){
    int inv_count = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] > arr[j])
                inv_count++;
    return inv_count;
}
    vector<int>adj[N];
    bool visited[N];
    vector<int> avic;
    void dfs(int v)
    {visited[v]=true;
      avic.pb(v);
    for(int i:adj[v])
    {
        if(!visited[i]){dfs(i);
        }
    }
}
int32_t main(){   
    int n;
    cin>>n;
    for(int i=0; i<n-1; i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);adj[v].push_back(u);
    }
    int ar[7]={0,0,1,166666669,166666681,500000007,500000009};
    dfs(1);
    int num=getInvCount(avic,n);
    if(n<7){
      cout<<(ar[n]);
    }
    else{
      cout<<((num*(inv(n))));
    }
    return 0;
}

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment