| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635525 |
2022-08-26T11:03:18 Z |
Mahdi |
Sumtree (INOI20_sumtree) |
C++17 |
|
553 ms |
28864 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5, NN=3e5+5, M=1e9+7;
int ans, q, n, r, st[N], ts[N], fn[N], siz[N], num[N], ss[N], pr[N][18];
int f[N+NN], rf[N+NN], cmo;
vector<int>g[N];
int tav(int a, int b){
int res=1;
while(b){
if(b&1)
res=1LL*res*a%M;
a=1LL*a*a%M;
b>>=1;
}
return res;
}
int C(int x, int y){
ll res=1LL*f[x]*rf[y]%M;
res=res*rf[x-y]%M;
return res;
}
void pre(){
f[0]=1;
for(int i=1;i<N+NN;++i)
f[i]=1LL*f[i-1]*i%M;
rf[N+NN-1]=tav(f[N+NN-1], M-2);
for(int i=N+NN-2;i>=0;--i)
rf[i]=1LL*(i+1)*rf[i+1]%M;
}
int ppp(int u, int t){
for(int i=0;t>0;++i){
if(t&1)
u=pr[u][i];
t>>=1;
}
return u;
}
struct seg_tree{
int sz, h[3*N], lz[3*N], a[3*N], b[3*N];
vector<int>ve;
vector<pii>ev;
seg_tree(){
sz=1;
while(sz<n)
sz<<=1;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(lz, 0, sizeof(lz));
fill(h, h+2*sz, 1);
}
int suma(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return 0;
if(lx>=l && rx<=r)
return a[x];
int m=(lx+rx)/2;
return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
}
void adda(int x, int v){
x=st[x];
x+=sz-1;
a[x]+=v;
while(x){
--x;
x/=2;
a[x]+=v;
}
}
int sumb(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return 0;
if(lx>=l && rx<=r)
return b[x];
int m=(lx+rx)/2;
return sumb(2*x+1, lx, m, l, r)+sumb(2*x+2, m, rx, l, r);
}
void addb(int x, int v){
x=st[x];
x+=sz-1;
b[x]+=v;
while(x){
--x;
x/=2;
b[x]+=v;
}
}
void add(int x, int lx, int rx, int l, int r, int t){
if(lx>=r || rx<=l)
return;
if(lx>=l && rx<=r){
h[x]+=t;
lz[x]+=t;
return;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
add(2*x+1, lx, m, l, r, t);
add(2*x+2, m, rx, l, r, t);
h[x]=-max(-h[2*x+1], -h[2*x+2]);
}
void add(int l, int r, int t){
add(0, 0, sz, l, r, t);
}
int min(int x, int lx, int rx, int i){
if(lx==rx-1)
return h[x];
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
if(i<m)
return min(2*x+1, lx, m, i);
return min(2*x+2, m, rx, i);
}
void opr(int x, int lx, int rx, int r){
if(lx>=r)
return;
if(rx<=r){
ve.push_back(x);
ev.push_back({lx, rx});
return;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
opr(2*x+2, m, rx, r);
opr(2*x+1, lx, m, r);
}
int fr(int x, int lx, int rx, int val){
if(lx+1==rx){
if(h[x]>=val)
return lx;
return rx;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
if(h[2*x+2]>=val)
return fr(2*x+1, lx, m, val);
return fr(2*x+2, m, rx, val);
}
int par(int u){
int uu=st[u];
int hh=min(0, 0, sz, uu);
int l=0, r=n;
while(l+1<r){
int m=(l+r)/2;
int w=ppp(u, m);
if(min(0, 0, sz, st[w])==hh)
l=m;
else
r=m;
}
return ppp(u, l);
/*cout<<"---------------------------------\n";
cout<<u<<' ';
u=st[u];
cout<<u<<'\n';
opr(0, 0, sz, u+1);
for(int i=0;i<ve.size();++i)
cout<<"tof : "<<ve[i]<<' '<<ev[i].F<<", "<<ev[i].S<<'\n';
int hh=min(0, 0, sz, u);
cout<<hh<<'\n';
int res=0;
for(int i=0;i<ve.size();++i){
if(h[ve[i]]<hh){
cout<<"fuck : "<<ve[i]<<'\n';
res=fr(ve[i], ev[i].F, ev[i].S, hh);
break;
}
}
cout<<res<<" "<<"aha\n";
ve.clear();
ev.clear();
return ts[res];*/
}
};
void dfs(int &tm, const int &v, const int &p=-1){
ts[tm]=v;
st[v]=tm++;
ss[v]=1;
for(int u: g[v]){
if(u!=p){
pr[u][0]=v;
for(int i=1;i<18;++i)
pr[u][i]=pr[pr[u][i-1]][i-1];
dfs(tm, u, v);
ss[v]+=ss[u];
}
}
fn[v]=tm;
}
void ud(const int &v){
if(num[v]<0)
--cmo;
else{
ans=1LL*ans*tav(C(num[v]+siz[v]-1, siz[v]-1), M-2)%M;
// cout<<"kok : "<<v<<" : "<<C(num[v]+siz[v]-1, siz[v]-1)<<'\n';
}
}
void du(const int &v){
if(num[v]<0)
++cmo;
else{
// cout<<"kko : "<<v<<", "<<num[v]<<", "<<siz[v]<<" "<<" : "<<C(num[v]+siz[v]-1, siz[v]-1)<<'\n';
ans=1LL*ans*C(num[v]+siz[v]-1, siz[v]-1)%M;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
pre();
cin>>n>>r;
for(int i=0;i<n-1;++i){
int u, v;
cin>>u>>v;
g[--u].push_back(--v);
}
int tm=0;
dfs(tm, 0);
seg_tree A;
ans=C(r+n-1, n-1);
cout<<ans<<'\n';
siz[0]=n;
num[0]=r;
cin>>q;
while(q--){
int t, u;
cin>>t>>u;
--u;
if(t==1){
int v;
cin>>v;
int w=A.par(u);
//cout<<"par = "<<w<<'\n';
A.add(st[u], fn[u], 1);
ud(w);
siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
A.adda(u, siz[u]);
siz[w]-=siz[u];
A.adda(w, -siz[u]);
num[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
A.addb(u, num[u]);
num[w]-=num[u];
A.addb(w, -num[u]);
du(w);
du(u);
}
else{
A.add(st[u], fn[u], -1);
int w=A.par(u);
// cout<<"par = "<<u<<", "<<w<<'\n';
ud(w);
ud(u);
A.adda(u, -siz[u]);
siz[w]+=siz[u];
A.adda(w, siz[u]);
A.addb(u, -num[u]);
num[w]+=num[u];
A.addb(w, num[u]);
siz[u]=num[u]=0;
du(w);
}
if(cmo==0)
cout<<ans<<'\n';
else
cout<<0<<'\n';
//cout<<"fuck : "<<cmo<<", "<<ans<<'\n';
/*for(int i=0;i<n;++i)
cout<<siz[i]<<' ';
cout<<'\n';
for(int i=0;i<n;++i)
cout<<num[i]<<' ';
cout<<'\n';*/
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
23116 KB |
Output is correct |
| 2 |
Correct |
66 ms |
23024 KB |
Output is correct |
| 3 |
Correct |
77 ms |
23096 KB |
Output is correct |
| 4 |
Correct |
80 ms |
23084 KB |
Output is correct |
| 5 |
Correct |
93 ms |
23372 KB |
Output is correct |
| 6 |
Correct |
16 ms |
18380 KB |
Output is correct |
| 7 |
Correct |
15 ms |
18516 KB |
Output is correct |
| 8 |
Correct |
15 ms |
18388 KB |
Output is correct |
| 9 |
Correct |
67 ms |
23536 KB |
Output is correct |
| 10 |
Correct |
68 ms |
23612 KB |
Output is correct |
| 11 |
Correct |
72 ms |
24272 KB |
Output is correct |
| 12 |
Correct |
93 ms |
28864 KB |
Output is correct |
| 13 |
Correct |
67 ms |
22676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
24652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
553 ms |
26252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
23116 KB |
Output is correct |
| 2 |
Correct |
66 ms |
23024 KB |
Output is correct |
| 3 |
Correct |
77 ms |
23096 KB |
Output is correct |
| 4 |
Correct |
80 ms |
23084 KB |
Output is correct |
| 5 |
Correct |
93 ms |
23372 KB |
Output is correct |
| 6 |
Correct |
16 ms |
18380 KB |
Output is correct |
| 7 |
Correct |
15 ms |
18516 KB |
Output is correct |
| 8 |
Correct |
15 ms |
18388 KB |
Output is correct |
| 9 |
Correct |
67 ms |
23536 KB |
Output is correct |
| 10 |
Correct |
68 ms |
23612 KB |
Output is correct |
| 11 |
Correct |
72 ms |
24272 KB |
Output is correct |
| 12 |
Correct |
93 ms |
28864 KB |
Output is correct |
| 13 |
Correct |
67 ms |
22676 KB |
Output is correct |
| 14 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
