Submission #999138

#	Time	Username	Problem	Language	Result	Execution time	Memory
999138		vjudge1	Sumtree (INOI20_sumtree)	C++17	30 / 100	3094 ms	44232 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int MAXNC = 2*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))%mod;
    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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30