이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;
#define X first
#define Y second
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define mins(a,b) (a = min(a,b))
#define maxs(a,b) (a = max(a,b))
#define pb push_back
#define Mp make_pair
#define lc id<<1
#define rc lc|1
#define mid ((l+r)/2)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e9 + 23;
const ll MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int MXR = 5e5 + 5;
const int LOG = 23;
ll F[MXR], I[MXR];
ll C(int n, int r) {
return r<0||r>n ? 0 : F[n]*I[r]%MOD*I[n-r]%MOD;
}
ll IC(int n, int r) {
return F[r]*F[n-r]%MOD*I[n]%MOD;
}
int n, q, par[MXN], stt[MXN], fnt[MXN], timer, ver[MXN], fen[2][MXN], label[MXN];
int c0;
ll ans;
vector<int> g[MXN];
void dfs(int v) {
ver[stt[v] = ++timer] = v;
for(int u : g[v])
if(u^par[v])
par[u] = v,
dfs(u);
fnt[v] = timer;
}
void updx(int ind, int p, int x) {
for(p+=2; p<MXN; p+=p&-p) fen[ind][p] += x;
}
int getx(int ind, int p) {
int res=0;
for(p+=2; p; p-=p&-p) res += fen[ind][p];
return res;
}
int getr(int ind, int s, int e) {
return getx(ind, e) - getx(ind, s-1);
}
void add(int v) {
int sz = getr(0, stt[v], fnt[v]);
int R = label[v] - getr(1, stt[v], fnt[v]);
if(C(R+sz-1, sz-1)) (ans *= C(R+sz-1, sz-1)) %= MOD;
else c0++;
}
void rem(int v) {
int sz = getr(0, stt[v], fnt[v]);
int R = label[v] - getr(1, stt[v], fnt[v]);
if(C(R+sz-1, sz-1)) (ans *= IC(R+sz-1, sz-1)) %= MOD;
else c0--;
}
set<int> seg[MXN<<2];
void insert(int s, int e, int x, int l=1, int r=n+1, int id=1) {
if(s<=l && r<=e) {
seg[id].insert(x);
return;
}
if(s<mid) insert(s,e,x, l, mid, lc);
if(e>mid) insert(s,e,x, mid, r, rc);
}
void erase(int s, int e, int x, int l=1, int r=n+1, int id=1) {
if(s<=l && r<=e) {
seg[id].erase(x);
return;
}
if(s<mid) erase(s,e,x, l, mid, lc);
if(e>mid) erase(s,e,x, mid, r, rc);
}
int get_par(int p, int l=1, int r=n+1, int id=1) {
int res = (seg[id].empty() ? 0 : *seg[id].rbegin());
if(r-l > 1) {
if(p<mid) maxs(res, get_par(p, l, mid, lc));
else maxs(res, get_par(p, mid, r, rc));
}
return res;
}
#define ANS (c0 ? 0 : ans)
void Main() {
F[0] = 1;
for(int i=1; i<MXR; i++) F[i] = F[i-1]*i%MOD;
I[0] = I[1] = 1;
for(int i=2; i<MXR; i++) I[i] = (MOD-MOD/i)*I[MOD%i]%MOD;
for(int i=2; i<MXR; i++) (I[i] *= I[i-1]) %= MOD;
cin >> n >> label[1];
for(int i=1, u,v; i<n; i++) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1);
for(int i=1; i<=n; i++) updx(0, stt[i], 1);
insert(1, n+1, 1);
ans = 1;
add(1);
cout << ANS << '\n';
cin >> q;
while(q--) {
int t;
cin >> t;
if(t == 1) {
int v;
cin >> v;
cin >> label[v];
int u = ver[get_par(stt[v])];
insert(stt[v], fnt[v]+1, stt[v]);
rem(u);
add(v);
int sz = getr(0, stt[v], fnt[v]);
int R = label[v] - getr(1, stt[v], fnt[v]);
updx(0, stt[par[v]], -sz);
if(par[u]) updx(0, stt[par[u]], sz);
updx(1, stt[par[v]], R);
if(par[u]) updx(1, stt[par[u]], -R);
add(u);
}
else {
int v;
cin >> v;
erase(stt[v], fnt[v]+1, stt[v]);
int u = ver[get_par(stt[v])];
rem(v);
rem(u);
int sz = getr(0, stt[v], fnt[v]);
int R = label[v] - getr(1, stt[v], fnt[v]);
updx(0, stt[par[v]], sz);
if(par[u]) updx(0, stt[par[u]], -sz);
updx(1, stt[par[v]], -R);
if(par[u]) updx(1, stt[par[u]], R);
add(u);
}
cout << ANS << '\n';
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int T = 1;
// cin >> T;
while(T--) Main();
return 0;
}
# | 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... |