| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 809233 |
2023-08-05T23:05:29 Z |
ashcomp |
Sumtree (INOI20_sumtree) |
C++14 |
|
146 ms |
197308 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 = 3e5 + 10;
const ll N = 2e6 + 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[N] , inv[N];
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(ll i=1; i<N; i++){
fac[i] = (fac[i-1] * i)%mod;
}
inv[N-1] = pw(fac[N-1],mod-2);
for(ll i=N-1; i>0; i--){
inv[i-1] = (inv[i]*i)%mod;
}
for(ll i=1; i<N; i++){
sz[i] = 1;
}
}//ok
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]);
}
}//ok
struct PAR_segment{
set<pll> seg[maxn<<2];
void build(ll tl=1 , ll tr=n , ll 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{
ll fen[maxn];
void upd(ll pos , ll val)
{
for(; pos<=n; pos+=(pos&-pos)){
fen[pos]+=val;
}
}
ll find(ll pos)
{
ll res = 0;
for(; pos>0; pos-=(pos&-pos)){
res += fen[pos];
}
return res;
}
ll ask(ll l , ll r)
{
return find(r)-find(l-1);
}
};//ok
PAR_segment Par;
SZ_segment Sz , Val;
ll 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++){
ll 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.upd(st[1],n);
Val.upd(st[1],k);
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;
X -= Val.ask(st[v],en[v]);
Val.upd(st[v],X);
ll siz=sz[v] - Sz.ask(st[v],en[v]);
Sz.upd(st[v],siz);
pll e = Par.ask(st[v]);ll p = e.S;
Par.upd({-h[v],v},st[v],en[v]);
Val.upd(st[p],-X);
Sz.upd(st[p],-siz);
//cout<<p<<" , "<<siz<<" , "<<X<<"\n";
/**/
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);
/**/
}else{
ll v; cin>>v;
Par.del({-h[v],v},st[v],en[v]);
pll e = Par.ask(st[v]);ll p = e.S;
ll siz = cnt[v];
Val.upd(st[v],-temp[v]);
Val.upd(st[p],temp[v]);
Sz.upd(st[v],-siz);
Sz.upd(st[p],siz);
/**/
ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ll y = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
x = (y*x)%mod;
ans = (ans * pw(x,mod-2))%mod;
cnt[p] += siz;
cnt[v] -= siz;
temp[p] += temp[v];
temp[v] -= temp[v];
x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
ans = (ans * x)%mod;
ANS.push_back(ans);
/**/
}
}
for(auto u : ANS){
cout<<u<<"\n";
}
return 0;
}
/*
4 3
1 2
2 3
2 4
2
1 3 1
1 2 1
*/
/*
*/
/*
by
_____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \
/::\ \ /::\ \ /::\____\ /::\ \
/::::\ \ /::::\ \ /:::/ / \:::\ \
/::::::\ \ /::::::\ \ /:::/ / \:::\ \
/:::/\:::\ \ /:::/\:::\ \ /:::/ / \:::\ \
/:::/__\:::\ \ /:::/__\:::\ \ /:::/____/ \:::\ \
/::::\ \:::\ \ \:::\ \:::\ \ /::::\ \ /::::\ \
/::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \ _____ ____ /::::::\ \
/:::/\:::\ \:::\ \ /\ \:::\ \:::\ \ /:::/\:::\ \ /\ \ /\ \ /:::/\:::\ \
/:::/ \:::\ \:::\____\/::\ \:::\ \:::\____\/:::/ \:::\ /::\____\/::\ \/:::/ \:::\____\
\::/ \:::\ /:::/ /\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /\:::\ /:::/ \::/ /
\/____/ \:::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / \:::\/:::/ / \/____/
\::::::/ / \:::\ \:::\ \ \::::::/ / \::::::/ /
\::::/ / \:::\ \:::\____\ \::::/ / \::::/____/
/:::/ / \:::\ /:::/ / /:::/ / \:::\ \
/:::/ / \:::\/:::/ / /:::/ / \:::\ \
/:::/ / \::::::/ / /:::/ / \:::\ \
/:::/ / \::::/ / /:::/ / \:::\____\
\::/ / \::/ / \::/ / \::/ /
\/____/ \/____/ \/____/ \/____/
*/
//NOGHRE SHODANAM BAD NIST :_)
Compilation message
Main.cpp: In function 'void preps()':
Main.cpp:63:23: warning: iteration 300009 invokes undefined behavior [-Waggressive-loop-optimizations]
63 | sz[i] = 1;
| ~~~~~~^~~
Main.cpp:62:22: note: within this loop
62 | for(ll i=1; i<N; i++){
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
197284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
197308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
197264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
197212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
197284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
