#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 seg[(1<<20)];
segres(){
for(long long i=kaf;i<(1<<20);i++){
seg[i]=-1;
}
for(long long i=1;i<kaf;i++){
seg[i]=-1;
}
}
void upd(long long i,long long w){
if(i==0)
{
return ;
}
if(i>=kaf){
seg[i]=w;
return upd((i>>1),w);
}
////cout<<i<<" "<<w<<" "<<seg[(i<<1)]<<" "<<seg[(i<<1)^1]<<"\n";
if((seg[(i<<1)])==-1&&seg[(i<<1)^1]==-1){
seg[i]=-1;
return upd((i>>1),w);
}
if((seg[(i<<1)])==-1){
seg[i]=seg[(i<<1)^1];
return upd((i>>1),w);
}
if(seg[(i<<1)^1]==-1){
seg[i]=seg[(i<<1)];
return upd((i>>1),w);
}
seg[i]=1ll*seg[(i<<1)]*seg[(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);
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);
//cout<<tedp<<" asd "<<val[pp]<<" "<<jamp<<" "<<ted<<" "<<fake<<"\n";
res.upd(kaf+stf[pp].first,-1);
res.upd(kaf+stf[pp].first,fake);
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.seg[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.seg[1]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
275 ms |
257036 KB |
Output is correct |
| 2 |
Correct |
274 ms |
257152 KB |
Output is correct |
| 3 |
Correct |
277 ms |
257104 KB |
Output is correct |
| 4 |
Correct |
295 ms |
257036 KB |
Output is correct |
| 5 |
Correct |
253 ms |
254248 KB |
Output is correct |
| 6 |
Correct |
185 ms |
230624 KB |
Output is correct |
| 7 |
Correct |
186 ms |
230348 KB |
Output is correct |
| 8 |
Correct |
186 ms |
230336 KB |
Output is correct |
| 9 |
Correct |
291 ms |
249092 KB |
Output is correct |
| 10 |
Correct |
290 ms |
249068 KB |
Output is correct |
| 11 |
Correct |
290 ms |
249052 KB |
Output is correct |
| 12 |
Correct |
283 ms |
248096 KB |
Output is correct |
| 13 |
Correct |
281 ms |
255488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
230132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
500 ms |
539160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
646 ms |
261012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
275 ms |
257036 KB |
Output is correct |
| 2 |
Correct |
274 ms |
257152 KB |
Output is correct |
| 3 |
Correct |
277 ms |
257104 KB |
Output is correct |
| 4 |
Correct |
295 ms |
257036 KB |
Output is correct |
| 5 |
Correct |
253 ms |
254248 KB |
Output is correct |
| 6 |
Correct |
185 ms |
230624 KB |
Output is correct |
| 7 |
Correct |
186 ms |
230348 KB |
Output is correct |
| 8 |
Correct |
186 ms |
230336 KB |
Output is correct |
| 9 |
Correct |
291 ms |
249092 KB |
Output is correct |
| 10 |
Correct |
290 ms |
249068 KB |
Output is correct |
| 11 |
Correct |
290 ms |
249052 KB |
Output is correct |
| 12 |
Correct |
283 ms |
248096 KB |
Output is correct |
| 13 |
Correct |
281 ms |
255488 KB |
Output is correct |
| 14 |
Incorrect |
190 ms |
230132 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
