#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=2000000+10,maxm=5000000+10;
vector<long long>adj[maxn],child[maxn];
long long par[maxn],val[maxn],link[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<long long,long long>stf[maxn];
long long kaf=(1<<19);
struct segment{
set<pair<long long,long long>>seg[(1<<20)];
pair<long long,long long> get(long long i){
if(i==0){
return make_pair(0,0);
}
if((long long)seg[i].size()==0){
return get((i>>1));
}
auto x=*seg[i].rbegin();
return max(get((i>>1)),x);
}
void del(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i].erase(make_pair(high[w],w));
return ;
}
long long m=(l+r)>>1;
del((i<<1),l,m,tl,tr,w);
del((i<<1)^1,m+1,r,tl,tr,w);
}
void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i].insert(make_pair(high[w],w));
return ;
}
long long m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
}
}segbal;
struct segjam{
long long seg[(1<<20)];
long long pors(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i];
}
long long m=(l+r)>>1;
long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
return ret;
}
void upd(long long i,long long w){
if(i==0){
return ;
}
seg[i]+=w;
upd((i>>1),w);
}
}segjam,segted;
struct segres{
long long sega[(1<<20)];
segres(){
for(long long i=kaf;i<(1<<20);i++){
sega[i]=-1;
}
for(long long i=1;i<kaf;i++){
sega[i]=-1;
}
}
void upd(long long i,long long w){
if(i==0)
{
return ;
}
//return ;
if(i<0||i>=(1<<20)){
return ;
}
if((i<<1)>=(1<<20)){
//return ;
sega[i]=w;
//return ;
return upd((i>>1),w);
}
// return ;
////cout<<i<<" "<<w<<" "<<seg[(i<<1)]<<" "<<seg[(i<<1)^1]<<"\n";
if((sega[(i<<1)])==-1&&sega[(i<<1)^1]==-1){
sega[i]=-1;
return upd((i>>1),w);
}
//return ;
if((sega[(i<<1)])==-1){
sega[i]=sega[(i<<1)^1];
return upd((i>>1),w);
}
if(sega[(i<<1)^1]==-1){
sega[i]=sega[(i<<1)];
return upd((i>>1),w);
}
sega[i]=1ll*sega[(i<<1)]*sega[(i<<1)^1]%mod;
return upd((i>>1),w);
}
}res;
long long mypow(long long m,long long y){
if(y==0){
return 1;
}
long long p=mypow(m,(y>>1));
p*=p;
p%=mod;
if(y&1){
p*=m;
p%=mod;
}
return p;
}
void aval(){
fact[0]=1;
for(long long i=1;i<maxm;i++){
fact[i]=1ll*fact[i-1]*i%mod;
}
revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
for(long long i=maxm-2;i>=0;i--){
revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
}
}
long long c(long long i,long long j){
//cout<<"av: "<<i<<" "<<j<<"\n";
if(i<0||j<0||i<j){
return 0;
}
//cout<<"dov: "<<i<<" "<<j<<"\n";
long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
return ret;
}
void dfs(long long u,long long para=0){
cnt[u]=1;
high[u]=high[para]+1;
timea++;
stf[u].first=timea;
par[u]=para;
for(auto x:adj[u]){
if(x!=para){
child[u].push_back(x);
dfs(x,u);
cnt[u]+=cnt[x];
}
}
stf[u].second=timea;
}
long long hes(long long a,long long b){
a++;
//cout<<"wtf: "<<a<<" "<<b<<"\n";
long long ret=c(b+a-1,a-1);
return ret;
}
void tof(){
//cout<<"salam"<<endl;
res.upd(stf[1].first+kaf,hes(n-1,val[1]));
//cout<<"vas "<<n-1<<" "<<val[1]<<" "<<hes(n-1,val[1])<<endl;
segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
//cout<<"akh"<<endl;
link[1]=0;
}
void upd(long long u,long long w){
wa[u]=w;
val[u]=w;
long long pp=segbal.get(stf[u].first+kaf).second;
long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//return ;
segted.upd(kaf+stf[u].first,ted);
segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
segjam.upd(kaf+stf[u].first,-jam+w);
//return ;
long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
long long fake=hes(tedp-1,val[pp]-jamp);
//return ;
//cout<<tedp<<" asd "<<val[pp]<<" "<<jamp<<" "<<ted<<" "<<fake<<"\n";
res.upd(kaf+stf[pp].first,fake);
// return ;
// if(kaf+stf[pp].first>=(1<<20)){
// return ;
// }
// res.upd(kaf+stf[pp].first,fake);
//return ;
fake=hes(ted-1,val[u]-jam);
//cout<<ted<<" sec "<<val[u]<<" "<<jam<<"\n";
res.upd(stf[u].first+kaf,fake);
}
void del(long long u){
long long pp=segbal.get(stf[u].first+kaf).second;
long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
segted.upd(kaf+stf[u].first,-ted);
segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
segjam.upd(kaf+stf[u].first,+jam-wa[u]);
long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
long long fake=hes(tedp-1,val[pp]-jamp);
res.upd(kaf+stf[pp].first,-1);
res.upd(kaf+stf[pp].first,fake);
res.upd(stf[u].first+kaf,-1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
aval();
cin>>n>>k;
for(long long i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
segjam.upd(stf[1].first+kaf,k);
////cout<<"salam"<<endl;
val[1]=k;
tof();
//cout<<"salam"<<endl;
long long q;
cin>>q;
asd=1;
cout<<res.sega[1]<<"\n";
for(;asd<=q;asd++){
long long qq;
cin>>qq;
if(qq==1){
long long u,w;
cin>>u>>w;
upd(u,w);
}
else{
long long u;
cin>>u;
del(u);
}
cout<<res.sega[1]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
271 ms |
257076 KB |
Output is correct |
| 2 |
Correct |
272 ms |
257108 KB |
Output is correct |
| 3 |
Correct |
292 ms |
257116 KB |
Output is correct |
| 4 |
Correct |
282 ms |
257084 KB |
Output is correct |
| 5 |
Correct |
256 ms |
254324 KB |
Output is correct |
| 6 |
Correct |
183 ms |
230584 KB |
Output is correct |
| 7 |
Correct |
190 ms |
230468 KB |
Output is correct |
| 8 |
Correct |
183 ms |
230328 KB |
Output is correct |
| 9 |
Correct |
290 ms |
249068 KB |
Output is correct |
| 10 |
Correct |
338 ms |
249080 KB |
Output is correct |
| 11 |
Correct |
312 ms |
249136 KB |
Output is correct |
| 12 |
Correct |
280 ms |
248188 KB |
Output is correct |
| 13 |
Correct |
279 ms |
255260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
230060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
516 ms |
539164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
667 ms |
259288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
271 ms |
257076 KB |
Output is correct |
| 2 |
Correct |
272 ms |
257108 KB |
Output is correct |
| 3 |
Correct |
292 ms |
257116 KB |
Output is correct |
| 4 |
Correct |
282 ms |
257084 KB |
Output is correct |
| 5 |
Correct |
256 ms |
254324 KB |
Output is correct |
| 6 |
Correct |
183 ms |
230584 KB |
Output is correct |
| 7 |
Correct |
190 ms |
230468 KB |
Output is correct |
| 8 |
Correct |
183 ms |
230328 KB |
Output is correct |
| 9 |
Correct |
290 ms |
249068 KB |
Output is correct |
| 10 |
Correct |
338 ms |
249080 KB |
Output is correct |
| 11 |
Correct |
312 ms |
249136 KB |
Output is correct |
| 12 |
Correct |
280 ms |
248188 KB |
Output is correct |
| 13 |
Correct |
279 ms |
255260 KB |
Output is correct |
| 14 |
Incorrect |
187 ms |
230060 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
