| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 809214 |
2023-08-05T22:09:56 Z |
ashcomp |
Sumtree (INOI20_sumtree) |
C++14 |
|
515 ms |
199220 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O2")
typedef long long ll;
typedef double db;
const ll INF = 1e9;
const ll maxn = 5e5 + 10;
const ll mod = 1e9 + 7;
ll n , q , k , sz[maxn] , st[maxn] , en[maxn] , h[maxn] , ti=1 , ans;
vector<ll> g[maxn] , ANS;
ll fac[maxn] , inv[maxn];
ll pw(ll a , ll b)
{
ll res = 1;
while(b){
if(b&1)res = (res*a)%mod;
b>>=1; a=(a*a)%mod;
}
return res;
}
ll choose(ll a , ll b)
{
if(b>a || b<0)return 0;
ll A = fac[a];
ll B = (inv[b] * inv[a-b])%mod;
ll C = (A*B)%mod;
return C;
}
void preps()
{
fac[0] = 1;
for(int i=1; i<maxn; i++){
fac[i] = (fac[i-1] * i)%mod;
}
inv[maxn-1] = pw(fac[maxn-1],mod-2);
for(ll i=maxn-1; i>0; i--){
inv[i-1] = (inv[i]*i)%mod;
}
for(int i=1; i<maxn; i++){
sz[i] = 1;
}
}
void dfs(ll v , ll p)
{
st[v] = ti++;
en[v] = st[v];
for(auto u : g[v]){
if(u==p)continue;
h[u] = h[v] + 1;
dfs(u,v);
sz[v] += sz[u];
en[v] = max(en[v],en[u]);
}
}
struct PAR_segment{
set<pii> seg[maxn<<2];
void build(int tl=1 , int tr=n , int v=1)
{
seg[v].insert({INF,INF});
if(tl==tr)return;
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
build(tl,mid,ml);
build(mid+1,tr,mr);
}
void upd(pll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
{
if(l>r)return;
if(l==tl && r==tr){
seg[v].insert(val);
return;
}
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
upd(val,l,min(r,mid),tl,mid,ml);
upd(val,max(l,mid+1),r,mid+1,tr,mr);
}
void del(pll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
{
if(l>r)return;
if(l==tl && r==tr){
seg[v].erase(val);
return;
}
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
del(val,l,min(r,mid),tl,mid,ml);
del(val,max(l,mid+1),r,mid+1,tr,mr);
}
pll ask(ll pos , ll tl=1 , ll tr=n , ll v=1){
if(tl==tr){
pll res = *seg[v].begin();
return res;
}
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
pll res = *seg[v].begin() , e;
if(pos<=mid)e = ask(pos,tl,mid,ml);
else e = ask(pos,mid+1,tr,mr);
if(e.F < res.F){
return e;
}else{
return res;
}
}
};
struct SZ_segment{
pll seg[maxn<<2];
ll lazy[maxn<<2];
void build(int tl=1 , int tr=n , int v=1)
{
seg[v] = {1 , tr-tl+1};
if(tl==tr)return;
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
build(tl,mid,ml);
build(mid+1,tr,mr);
}
void shift(ll tl , ll tr , ll v)
{
ll ml=(v<<1) , mr=(v<<1)|1;
seg[v].S += lazy[v];
if(tl!=tr){
lazy[ml] += lazy[v];
lazy[mr] += lazy[v];
}
lazy[v] = 0;
}
void upd(ll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
{
shift(tl,tr,v);
if(l>r)return;
if(l==tl && r==tr){
lazy[v] += val;
shift(tl,tr,v);
return;
}
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
upd(val,l,min(r,mid),tl,mid,ml);
upd(val,max(l,mid+1),r,mid+1,tr,mr);
if(seg[ml].F < seg[mr].F){
seg[v] = seg[ml];
return;
}
if(seg[mr].F < seg[ml].F){
seg[v] = seg[mr];
return;
}
seg[v] = {seg[ml].F , seg[ml].S+seg[mr].S};
}
pll ask(ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
{
shift(tl,tr,v);
if(l>r)return {INF,-1};
if(l==tl && r==tr){
return seg[v];
}
ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
pll e1 = ask(l,min(r,mid),tl,mid,ml);
pll e2 = ask(max(l,mid+1),r,mid+1,tr,mr);
if(e1.F < e2.S){
return e1;
}
if(e1.F > e2.S){
return e2;
}
return {e1.F , e1.S+e2.S};
}
};
PAR_segment Par;
SZ_segment Sz;
int cnt[maxn] , temp[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
preps();
cin>>n>>k;
for(int i=1; i<n; i++){
int v,u; cin>>v>>u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1,1);
/**/
ans = choose(k+sz[1]-1 , sz[1]-1);
ANS.push_back(ans);
Par.build();
Par.upd({-h[1],1},1,n);
Sz.build();
//Sz.upd(1,1,n);
cnt[1] = n;
temp[1] = k;
/**/
cin>>q;
for(int i=1; i<=q; i++){
int tp; cin>>tp;
if(tp==1){
ll v,X; cin>>v>>X;
pll e = Par.ask(st[v]);ll p = e.S;
e = Sz.ask(st[v],en[v]); ll siz=e.S;
/**/
ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ans = (ans * pw(x,mod-2))%mod;
cnt[p] -= siz;
cnt[v] += siz;
temp[p] -= X;
temp[v] += X;
x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ans = (ans * x)%mod;
x = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
ans = (ans * x)%mod;
ANS.push_back(ans);
/**/
Par.upd({-h[v],v},st[v],en[v]);
Sz.upd(1,st[v],en[v]);
}else{
int v; cin>>v;
Par.del({-h[v],v},st[v],en[v]);
pll e = Par.ask(st[v]);ll p = e.S;
e = Sz.ask(st[v],en[v]); ll siz=e.S;
//cout<<e.F<<" , "<<e.S<<"\n";
/**/
ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ll y = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
y = (y*x);
ans = (ans * pw(y,mod-2))%mod;
//cout<<cnt[p]<<" , "<<temp[p]<<"\n";
cnt[p] += siz;
cnt[v] -= siz;
temp[p] += temp[v];
temp[v] = 0;
//cout<<cnt[p]<<" , "<<temp[p]<<"\n";
x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ans = (ans * x)%mod;
ANS.push_back(ans);
/**/
Sz.upd(-1,st[v],en[v]);
}
}
for(auto u : ANS)cout<<u<<" ";
return 0;
}
/*
3 2
1 2
2 3
2
1 2 1
2 2
*/
/*
*/
/*
by
_____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \
/::\ \ /::\ \ /::\____\ /::\ \
/::::\ \ /::::\ \ /:::/ / \:::\ \
/::::::\ \ /::::::\ \ /:::/ / \:::\ \
/:::/\:::\ \ /:::/\:::\ \ /:::/ / \:::\ \
/:::/__\:::\ \ /:::/__\:::\ \ /:::/____/ \:::\ \
/::::\ \:::\ \ \:::\ \:::\ \ /::::\ \ /::::\ \
/::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \ _____ ____ /::::::\ \
/:::/\:::\ \:::\ \ /\ \:::\ \:::\ \ /:::/\:::\ \ /\ \ /\ \ /:::/\:::\ \
/:::/ \:::\ \:::\____\/::\ \:::\ \:::\____\/:::/ \:::\ /::\____\/::\ \/:::/ \:::\____\
\::/ \:::\ /:::/ /\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /\:::\ /:::/ \::/ /
\/____/ \:::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / \:::\/:::/ / \/____/
\::::::/ / \:::\ \:::\ \ \::::::/ / \::::::/ /
\::::/ / \:::\ \:::\____\ \::::/ / \::::/____/
/:::/ / \:::\ /:::/ / /:::/ / \:::\ \
/:::/ / \:::\/:::/ / /:::/ / \:::\ \
/:::/ / \::::::/ / /:::/ / \:::\ \
/:::/ / \::::/ / /:::/ / \:::\____\
\::/ / \::/ / \::/ / \::/ /
\/____/ \/____/ \/____/ \/____/
*/
//NOGHRE SHODANAM BAD NIST :_)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
191692 KB |
Output is correct |
| 2 |
Correct |
188 ms |
191736 KB |
Output is correct |
| 3 |
Correct |
177 ms |
191692 KB |
Output is correct |
| 4 |
Correct |
169 ms |
191688 KB |
Output is correct |
| 5 |
Correct |
165 ms |
185976 KB |
Output is correct |
| 6 |
Correct |
72 ms |
149872 KB |
Output is correct |
| 7 |
Correct |
68 ms |
149456 KB |
Output is correct |
| 8 |
Correct |
68 ms |
149584 KB |
Output is correct |
| 9 |
Correct |
167 ms |
182524 KB |
Output is correct |
| 10 |
Correct |
172 ms |
182264 KB |
Output is correct |
| 11 |
Correct |
187 ms |
182492 KB |
Output is correct |
| 12 |
Correct |
156 ms |
180768 KB |
Output is correct |
| 13 |
Correct |
156 ms |
188368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
149164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
199220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
515 ms |
192364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
191692 KB |
Output is correct |
| 2 |
Correct |
188 ms |
191736 KB |
Output is correct |
| 3 |
Correct |
177 ms |
191692 KB |
Output is correct |
| 4 |
Correct |
169 ms |
191688 KB |
Output is correct |
| 5 |
Correct |
165 ms |
185976 KB |
Output is correct |
| 6 |
Correct |
72 ms |
149872 KB |
Output is correct |
| 7 |
Correct |
68 ms |
149456 KB |
Output is correct |
| 8 |
Correct |
68 ms |
149584 KB |
Output is correct |
| 9 |
Correct |
167 ms |
182524 KB |
Output is correct |
| 10 |
Correct |
172 ms |
182264 KB |
Output is correct |
| 11 |
Correct |
187 ms |
182492 KB |
Output is correct |
| 12 |
Correct |
156 ms |
180768 KB |
Output is correct |
| 13 |
Correct |
156 ms |
188368 KB |
Output is correct |
| 14 |
Incorrect |
67 ms |
149164 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
