oj.uz

Submission #999136

# Submission time Handle Problem Language Result Execution time Memory
999136 2024-06-15T07:17:23 Z vjudge1 Sumtree (INOI20_sumtree) C++17
0 / 100
 2 ms 1884 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
const int MAXNC = 5*N;
const int mod = 1e9+7;
vector<int> g[N];
long long fact[MAXNC];
int sz[N], tagsm[N];
int tag[N], tmptag[N];
long long binpow(long long a, long long b) {
  long long res = 1;
  while(b) {
    if(b&1) {
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    b>>=1;
  }
  return res;
}
long long ncr(long long nn, long long rr) {
  if(rr > nn)return 0;
  if(rr < 0)return 0;
  long long res = fact[nn];
  res = (res*binpow(fact[rr], mod-2))%mod;
  res = (res*binpow(fact[nn-rr], mod-2))%mod;
  return res;
}
long long ans=1;
void dfs(int at, int p) {
  sz[at]=1;
  tagsm[at]=0;
  for(int to:g[at]) {
    if(to == p)continue;
    dfs(to, at);
    sz[at]+=sz[to];
    tagsm[at] += tagsm[to];
  }
  if(tag[at] != -1) {
    long long tmp = tag[at]-tagsm[at];
//    cout << tmp << " " << sz[at] << endl;
    ans=(ans*ncr(sz[at]+tmp-1, tmp));
    sz[at]=0;
    tagsm[at] = tag[at];
  }

}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  fact[0] = 1;
  for(int i = 1;i<MAXNC;i++)fact[i] = (fact[i-1]*i)%mod;
  int n, r;
  cin >> n >> r;
  memset(tag, -1, sizeof tag);
  memset(tmptag, -1, sizeof tmptag);
  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;
  tag[1] = r;
  dfs(1, 0);
  cout << ans << "\n";
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
      tag[u]=v;
    }
    else {
      int u;
      cin >> u;
      tag[u]=-1;
    }
    ans=1;
    dfs(1, 0);
    cout << ans << "\n";
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -