Submission #999092

#	Time	Username	Problem	Language	Result	Execution time	Memory
999092		vjudge1	Sumtree (INOI20_sumtree)	C++17	10 / 100	369 ms	47036 KiB

Main

#include <bits/stdc++.h>

#define int long long
// #define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 1e6 + 5, LOGMAX = 20, B = 800, MOD = 1e9 + 7;

// int tree[4 * MAX], lazy[4 * MAX];

// void relax(int node, int l, int r){
//     if(!lazy[node]) return;
//     tree[node] += lazy[node];
//     if(l != r){
//         lazy[2 * node] += lazy[node];
//         lazy[2 * node + 1] += lazy[node];
//     }
//     lazy[node] = 0;
// }

// void update(int node, int l, int r, int ul, int ur, int val){
//     relax(node, l, r);
//     if(ur < l || r < ul) return;
//     if(ul <= l && r <= ur){
//         lazy[node] += val;
//         relax(node, l, r);
//         return;
//     }
//     int mid = (l + r) / 2;
//     update(2 * node, l, mid, ul, ur, val);
//     update(2 * node + 1, mid + 1, r, ul, ur, val);
//     tree[node] = max(tree[2 * node], tree[2 * node + 1]);
// }

// int ask(int node, int l, int r, int ql, int qr){
//     if(qr < l || r < ql) return 0;
//     relax(node, l, r);
//     if(ql <= l && r <= qr) return tree[node];
//     int mid = (l + r) / 2;
//     return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
// }

int f[MAX];
int invf[MAX];

int Cnk(int n, int k){
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}

int binpow(int a, int b){
    if(b == 0) return 1;
    if(b & 1) return binpow(a, b - 1) % MOD * a % MOD;
    else return binpow(a * a % MOD, b / 2) % MOD;
}
int inv(int a){
    return binpow(a, MOD - 2);
}

vector<int> g[MAX];

void solve(){
    int n, r; cin >> n >> r;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int q; cin >> q;
    int ans = 0;
    f[0] = 1;
    invf[0] = 1;
    for(int i = 1; i < MAX; i++){
        f[i] = f[i - 1] * i % MOD;
        invf[i] = invf[i - 1] * inv(i) % MOD;
    }
    for(int i = 0; i <= r; i++){
        ans = (ans + Cnk(i + n - 2, n - 2)) % MOD;
    }
    cout << ans << '\n';
}   

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30