This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |