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>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define err(x) cerr<<#x<<"="<<x<<'\n'
#define lc 2*id
#define rc 2*id+1
#define int mid=(r+l)/2
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define pb push_back
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define bit(i,j) ((j>>i)&1)
using namespace std;
const int md=1e9+7;
const int N=5e5+4;
const int NN=2e5+4;
int n;
vector<int> adj[NN];
int fct[N],inv[N];
int ans,t;
int sz[NN],h[NN],st[NN],en[NN],tme;
int A[NN],B[NN];
struct fenwick{
int fen[NN];
void add(int k,int x){
while(k<NN){
fen[k]+=x;
k+=(k&(-k));
}
}
int Get(int k){
int rt=0;
while(k>0){
rt+=fen[k];
k-=(k&(-k));
}
return rt;
}
int get(int l,int r){
return (Get(r)-Get(l-1));
}
}; fenwick f1,f2;
struct PQ{
priority_queue<pii> pq1;
priority_queue<pii> pq2;
void add(pii x){
pq1.push(x);
}
void erase(pii x){
pq2.push(x);
}
int get(){
while(!pq2.empty()&&pq1.top()==pq2.top()) pq1.pop(),pq2.pop();
if(pq1.empty()) return 0;
return (pq1.top().S);
}
};
PQ seg[4*NN];
void upd(int id,int l,int r,int v,int x){
if(st[v]>=r||(en[v]+1)<=l) return;
if(st[v]<=l&&(en[v]+1)>=r){
if(x==+1) seg[id].add({h[v],v});
else seg[id].erase({h[v],v});
return;
}
dmid;
upd(lc,l,mid,v,x);
upd(rc,mid,r,v,x);
}
int get(int id,int l,int r,int v){
if(st[v]<l||st[v]>=r) return 0;
int rt=seg[id].get();
if(l+1==r) return rt;
dmid;
int x1=get(lc,l,mid,v);
int x2=get(rc,mid,r,v);
if(h[x1]>h[rt]) rt=x1;
if(h[x2]>h[rt]) rt=x2;
return rt;
}
int pw(int a,int b){
int rt=1;
while(b){
if(b&1) rt=1LL*rt*a%md;
a=1LL*a*a%md;
b/=2;
}
return rt;
}
int C(int r,int _n){
if(r<0||r>_n) return 1;
return (1LL*(1LL*fct[_n]*inv[r]%md)*inv[_n-r]%md);
}
void dfs(int v,int p){
h[v]=h[p]+1;
st[v]=++tme;
sz[v]=1;
for(int u:adj[v]) if(u!=p){ dfs(u,v); sz[v]+=sz[u];}
en[v]=tme;
}
void add(int v,int w){
int par=get(1,1,n+1,v);
upd(1,1,n+1,v,+1);
f1.add(st[par],-A[par]);
f2.add(st[par],-B[par]);
ans=1LL*ans*pw(C(B[par],A[par]+B[par]-1),md-2)%md;
if(B[par]<0) t--;
A[v]=sz[v]-f1.get(st[v],en[v]);
B[v]=w-f2.get(st[v],en[v]);
A[par]-=A[v];
B[par]-=B[v];
f1.add(st[par],A[par]);
f1.add(st[v],A[v]);
f2.add(st[par],B[par]);
f2.add(st[v],B[v]);
if(B[v]<0) t++;
if(B[par]<0) t++;
ans=1LL*ans*C(B[par],A[par]+B[par]-1)%md;
ans=1LL*ans*C(B[v],A[v]+B[v]-1)%md;
}
void OUT(){
if(t>0){ cout<<"0\n"; return; }
cout<<ans<<'\n';
}
int32_t main(){
iostream::sync_with_stdio(0); cin.tie(0);
fct[0]=1; FOR(i,1,N-1) fct[i]=1LL*fct[i-1]*i%md;
inv[N-1]=pw(fct[N-1],md-2); FORR(i,N-2,0) inv[i]=1LL*inv[i+1]*(i+1)%md;
int k; cin>>n>>k;
FOR(i,1,n-1){
int u,v; cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1,1);
ans=C(k,k+n-1);
t=0;
A[1]=n;
B[1]=k;
f1.add(st[1],A[1]);
f2.add(st[1],B[1]);
upd(1,1,n+1,1,+1);
OUT();
int q; cin>>q;
while(q--){
int id,v,w;
cin>>id>>v;
assert(id==1);
if(id==1){
cin>>w;
add(v,w);
}//else rm(v);
OUT();
}
return 0;
}
Compilation message (stderr)
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:22:7: note: in expansion of macro 'int'
22 | const int md=1e9+7;
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:23:7: note: in expansion of macro 'int'
23 | const int N=5e5+4;
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:24:7: note: in expansion of macro 'int'
24 | const int NN=2e5+4;
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:25:1: note: in expansion of macro 'int'
25 | int n;
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:26:8: note: in expansion of macro 'int'
26 | vector<int> adj[NN];
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:26:8: note: in expansion of macro 'int'
26 | vector<int> adj[NN];
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:26:8: note: in expansion of macro 'int'
26 | vector<int> adj[NN];
| ^~~
Main.cpp:26:11: error: template argument 1 is invalid
26 | vector<int> adj[NN];
| ^
Main.cpp:26:11: error: template argument 2 is invalid
Main.cpp:26:17: error: 'NN' was not declared in this scope; did you mean 'NAN'?
26 | vector<int> adj[NN];
| ^~
| NAN
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:27:1: note: in expansion of macro 'int'
27 | int fct[N],inv[N];
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:28:1: note: in expansion of macro 'int'
28 | int ans,t;
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:29:1: note: in expansion of macro 'int'
29 | int sz[NN],h[NN],st[NN],en[NN],tme;
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:30:1: note: in expansion of macro 'int'
30 | int A[NN],B[NN];
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:32:2: note: in expansion of macro 'int'
32 | int fen[NN];
| ^~~
Main.cpp:13:14: error: 'mid' has not been declared
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:33:11: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp:13:14: error: 'mid' has not been declared
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:33:17: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:39:2: note: in expansion of macro 'int'
39 | int Get(int k){
| ^~~
Main.cpp:13:14: error: 'mid' does not name a type
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:47:2: note: in expansion of macro 'int'
47 | int get(int l,int r){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:33:11: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:33:11: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:33:17: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:33:17: note: in expansion of macro 'int'
33 | void add(int k,int x){
| ^~~
Main.cpp: In member function 'void fenwick::add(int, int)':
Main.cpp:34:9: error: 'k' was not declared in this scope
34 | while(k<NN){
| ^
Main.cpp:34:11: error: 'NN' was not declared in this scope; did you mean 'NAN'?
34 | while(k<NN){
| ^~
| NAN
Main.cpp:35:4: error: 'fen' was not declared in this scope
35 | fen[k]+=x;
| ^~~
Main.cpp:35:12: error: 'x' was not declared in this scope
35 | fen[k]+=x;
| ^
Main.cpp: At global scope:
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:3:25: error: template argument 1 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:3:25: error: template argument 2 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:52:17: note: in expansion of macro 'pii'
52 | priority_queue<pii> pq1;
| ^~~
Main.cpp:52:20: error: template argument 1 is invalid
52 | priority_queue<pii> pq1;
| ^
Main.cpp:52:20: error: template argument 2 is invalid
Main.cpp:52:20: error: template argument 3 is invalid
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:3:25: error: template argument 1 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:3:25: error: template argument 2 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:53:17: note: in expansion of macro 'pii'
53 | priority_queue<pii> pq2;
| ^~~
Main.cpp:53:20: error: template argument 1 is invalid
53 | priority_queue<pii> pq2;
| ^
Main.cpp:53:20: error: template argument 2 is invalid
Main.cpp:53:20: error: template argument 3 is invalid
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:3:25: error: template argument 1 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:3:25: error: template argument 2 is invalid
3 | #define pii pair<int,int>
| ^
Main.cpp:54:11: note: in expansion of macro 'pii'
54 | void add(pii x){
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:18: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:13:14: error: 'mid' was not declared in this scope
13 | #define int mid=(r+l)/2
| ^~~
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:13:19: error: 'r' was not declared in this scope; did you mean 'rc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:13:21: error: 'l' was not declared in this scope; did you mean 'lc'?
13 | #define int mid=(r+l)/2
| ^
Main.cpp:3:22: note: in expansion of macro 'int'
3 | #define pii pair<int,int>
| ^~~
Main.cpp:57:13: note: in expansion of macro 'pii'
57 | void erase(pii x){
| ^~~
Main.cpp:3:25: error: template argument 1 is invalid
3 | #define pii pair<int,int>
|