Submission #935508

#	Time	Username	Problem	Language	Result	Execution time	Memory
935508		Mohammadamin__Sh	Sumtree (INOI20_sumtree)	C++17	30 / 100	3058 ms	46880 KiB

Main

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 5e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18 + 100;

int n , r ,q  , fact[maxn] , ans = 1, sub[maxn] , num[maxn] , sham[maxn];
vector<int> adj[maxn];
int is[maxn];

ll Power(ll x , ll y){
    if(y < 0 or x < 0) return 0;
    if(y == 0) return 1;
    ll tmp = Power(x , y/2);
    tmp = 1ll * tmp * tmp % MOD;
    if(y&1) tmp = 1ll * x * tmp % MOD;
    return tmp % MOD;
}

ll tarkib(int x , int y){
    if(x == 0 or x == y) return 1;
    if(x > y) return 0;
    ll zir = fact[x] * fact[y-x] % MOD;
    ll res = 1ll * fact[y] * Power(zir , MOD-2);
    return res%MOD;
}

void Pre(int v = 1 , int p = 0){
    sub[v] = 1;
    for(int u : adj[v]) {
        if(u != p){
            Pre(u , v);
            sub[v] += sub[u];
        }
    }
}

void Dfs(int v , int p){
    int sum = 0;
    for(int u : adj[v]){
        if(u == p) continue;
        Dfs(u , v);
        if(ans == 0) return;
        sum += num[u];
        sham[v] += sham[u];
    }
    if(is[v] != -1){
        if(is[v] < sum) {
            ans = 0;
            return;
        }
        ans = (ans * tarkib(sub[v] - sham[v] - 1 , is[v] - sum + sub[v] - sham[v] - 1)) % MOD;
        int x = ans;
        num[v] = is[v];
        sham[v] = sub[v];
    }
    else num[v] = sum;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);

    fact[0] = 1;
    for(int i = 1 ; i < maxn ; i++) fact[i] = (fact[i-1]*i) % MOD;
    memset(is , -1 , sizeof is);

    cin >> n >> r;
    is[1] = r;
    for(int i = 1 ; i <= n-1 ; i++){
        int u , v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    Pre();
    cin >> q;
    while(q--){
        int ty;
        cin >> ty;
        memset(sham , 0 , sizeof sham);
        memset(num , 0 , sizeof num);
        ans = 1;
        Dfs(1 , 0);
        cout << ans << '\n';
        if(ty == 1){
            int v , w;
            cin >> v >> w;
            is[v] = w;
        }
        else{
            int v;
            cin >> v;
            is[v] = -1;
        }
    }
    memset(sham , 0 , sizeof sham);
    memset(num , 0 , sizeof num);
    ans = 1;
    Dfs(1 , 0);
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void Dfs(long long int, long long int)':
Main.cpp:63:13: warning: unused variable 'x' [-Wunused-variable]
   63 |         int x = ans;
      |             ^

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