| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 809239 |
2023-08-05T23:26:48 Z |
ashcomp |
Sumtree (INOI20_sumtree) |
C++14 |
|
3000 ms |
259544 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 = 1e6 + 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<maxn; 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 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 Fenwick{
ll fen[maxn];
void upd(ll pos , ll val)
{
for(; pos<=n; pos+=(pos&-pos)){
fen[pos]=(fen[pos]+val)%mod;
}
}
ll find(ll pos)
{
ll res = 0;
for(; pos>0; pos-=(pos&-pos)){
res = (res+fen[pos])%mod;
}
return res;
}
ll ask(ll l , ll r)
{
return find(r)-find(l-1);
}
};//ok
Segment Par;
Fenwick 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);
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;
}else{
while(n){
cout<<"NO"<<endl;
}
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 = Sz.ask(st[v],st[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);
ans = (ans * pw(x,mod-2))%mod;
ans = (ans * pw(y,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 :_)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
128240 KB |
Output is correct |
| 2 |
Correct |
155 ms |
128252 KB |
Output is correct |
| 3 |
Correct |
157 ms |
128296 KB |
Output is correct |
| 4 |
Correct |
161 ms |
128332 KB |
Output is correct |
| 5 |
Correct |
150 ms |
122436 KB |
Output is correct |
| 6 |
Correct |
52 ms |
82508 KB |
Output is correct |
| 7 |
Correct |
46 ms |
82356 KB |
Output is correct |
| 8 |
Correct |
46 ms |
82348 KB |
Output is correct |
| 9 |
Correct |
151 ms |
119000 KB |
Output is correct |
| 10 |
Correct |
158 ms |
118900 KB |
Output is correct |
| 11 |
Correct |
203 ms |
118972 KB |
Output is correct |
| 12 |
Correct |
180 ms |
117124 KB |
Output is correct |
| 13 |
Correct |
147 ms |
124512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3053 ms |
91200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
137164 KB |
Output is correct |
| 2 |
Correct |
231 ms |
144668 KB |
Output is correct |
| 3 |
Correct |
204 ms |
138484 KB |
Output is correct |
| 4 |
Correct |
355 ms |
157492 KB |
Output is correct |
| 5 |
Correct |
807 ms |
208916 KB |
Output is correct |
| 6 |
Correct |
48 ms |
83020 KB |
Output is correct |
| 7 |
Correct |
46 ms |
82508 KB |
Output is correct |
| 8 |
Correct |
50 ms |
82888 KB |
Output is correct |
| 9 |
Correct |
407 ms |
138916 KB |
Output is correct |
| 10 |
Correct |
328 ms |
135632 KB |
Output is correct |
| 11 |
Correct |
296 ms |
134544 KB |
Output is correct |
| 12 |
Correct |
354 ms |
136424 KB |
Output is correct |
| 13 |
Correct |
714 ms |
259440 KB |
Output is correct |
| 14 |
Correct |
739 ms |
259544 KB |
Output is correct |
| 15 |
Correct |
731 ms |
259504 KB |
Output is correct |
| 16 |
Correct |
728 ms |
259448 KB |
Output is correct |
| 17 |
Correct |
722 ms |
259412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3069 ms |
132780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
128240 KB |
Output is correct |
| 2 |
Correct |
155 ms |
128252 KB |
Output is correct |
| 3 |
Correct |
157 ms |
128296 KB |
Output is correct |
| 4 |
Correct |
161 ms |
128332 KB |
Output is correct |
| 5 |
Correct |
150 ms |
122436 KB |
Output is correct |
| 6 |
Correct |
52 ms |
82508 KB |
Output is correct |
| 7 |
Correct |
46 ms |
82356 KB |
Output is correct |
| 8 |
Correct |
46 ms |
82348 KB |
Output is correct |
| 9 |
Correct |
151 ms |
119000 KB |
Output is correct |
| 10 |
Correct |
158 ms |
118900 KB |
Output is correct |
| 11 |
Correct |
203 ms |
118972 KB |
Output is correct |
| 12 |
Correct |
180 ms |
117124 KB |
Output is correct |
| 13 |
Correct |
147 ms |
124512 KB |
Output is correct |
| 14 |
Execution timed out |
3053 ms |
91200 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
