#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],fres[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 calc(int i){
if(seg[(i<<1)]==-1&&seg[(i<<1)^1]==-1){
seg[i]=-1;
return ;
}
if(seg[(i<<1)]==-1){
seg[i]=seg[(i<<1)^1];
return ;
}
if(seg[(i<<1)^1]==-1){
seg[i]=seg[(i<<1)];
return ;
}
seg[i]=1ll*seg[(i<<1)^1]*seg[(i<<1)]%mod;
return ;
}
void upd(int i,int l,int r,int tl,int tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
w%=mod;
seg[i]=w;
return ;
}
int m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
}
}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(){
for(int i=0;i<maxn;i++){
fres[i]=-1;
val[i]=-1;
}
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){
if(i<0||j<0||i<j){
return 0;
}
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++;
long long ret=c(b+a-1,a-1);
return ret;
}
int findp(int u,int av){
if(u==av||val[u]==-1){
return findp(par[u],av);
}
return u;
}
long long porsjam(int u,int av){
long long ret=0;
if(u!=av&&val[u]!=-1){
ret+=val[u];
return ret;
}
for(auto x:child[u]){
ret+=porsjam(x,av);
}
return ret;
}
long long porsted(int u,int av){
long long ret=0;
if(u!=av&&val[u]!=-1){
return ret;
}
for(auto x:child[u]){
ret+=porsted(x,av);
}
ret++;
return ret;
}
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 pp=findp(u,u);
long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
// long long jam=porsjam(u,u);
long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
// long long ted=porsted(u,u);
segted.upd(kaf+stf[u].first,ted);
segted.upd(kaf+stf[pp].first,-ted);
segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
segjam.upd(kaf+stf[u].first,-jam+w);
segjam.upd(kaf+stf[pp].first,+jam-w);
long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
// long long jamp=porsjam(pp,pp);
long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
// long long tedp=porsted(pp,pp);
long long fake=hes(tedp-1,val[pp]-jamp);
fres[stf[pp].first]=fake;
// cout<<u<<" "<<pp<<" "<<jamp<<" "<<val[pp]<<" "<<tedp<<"\n";
// res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
fake=hes(ted-1,val[u]-jam);
fres[stf[u].first]=fake;
// res.upd(1,0,kaf-1,stf[u].first,stf[u].first,fake);
}
void del(long long u){
long long pp=segbal.get(stf[u].first+kaf).second;
// long long pp=findp(u,u);
long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
// long long jam=porsjam(u,u);
long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
// long long ted=porsted(u,u);
val[u]=-1;
segted.upd(kaf+stf[u].first,-ted);
segted.upd(kaf+stf[pp].first,+ted);
segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
segjam.upd(kaf+stf[u].first,+jam-val[u]);
segjam.upd(kaf+stf[u].first,-jam+val[u]);
long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
// long long jamp=porsjam(pp,pp);
long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
// long long tedp=porsted(pp,pp);
long long fake=hes(tedp-1,val[pp]-jamp);
fres[stf[pp].first]=fake;
fres[stf[u].first]=-1;
// res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,-1);
// res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
// res.upd(1,0,kaf-1,stf[u].first,stf[u].first,-1);
// val[u]=-1;
}
void calres(){
long long ret=1;
for(int i=stf[1].first;i<=stf[1].second;i++){
// cout<<i<<" asd "<<fres[i]<<"\n";
if(fres[i]==-1){
continue;
}
ret*=fres[i];
ret%=mod;
}
cout<<ret<<"\n";
}
void tof(){
//cout<<porsted(1,1)<<" "<<porsjam(1,1)<<"\n";
fres[stf[1].first]=hes(porsted(1,1)-1,val[1]-porsjam(1,1));
// res.upd(1,0,kaf-1,stf[1].first,stf[1].first,hes(n-1,val[1]));
segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
link[1]=0;
}
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);
val[1]=k;
tof();
long long q;
cin>>q;
asd=1;
// cout<<res.seg[1]<<"\n";
calres();
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";
calres();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
295 ms |
289100 KB |
Output is correct |
| 2 |
Correct |
294 ms |
289100 KB |
Output is correct |
| 3 |
Correct |
288 ms |
289100 KB |
Output is correct |
| 4 |
Correct |
287 ms |
289100 KB |
Output is correct |
| 5 |
Correct |
263 ms |
286328 KB |
Output is correct |
| 6 |
Correct |
188 ms |
261800 KB |
Output is correct |
| 7 |
Correct |
190 ms |
261580 KB |
Output is correct |
| 8 |
Correct |
187 ms |
261616 KB |
Output is correct |
| 9 |
Correct |
301 ms |
281084 KB |
Output is correct |
| 10 |
Correct |
307 ms |
281164 KB |
Output is correct |
| 11 |
Correct |
300 ms |
281072 KB |
Output is correct |
| 12 |
Correct |
296 ms |
280096 KB |
Output is correct |
| 13 |
Correct |
280 ms |
287308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
261320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1451 ms |
299408 KB |
Output is correct |
| 2 |
Execution timed out |
3072 ms |
303564 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3087 ms |
288808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
295 ms |
289100 KB |
Output is correct |
| 2 |
Correct |
294 ms |
289100 KB |
Output is correct |
| 3 |
Correct |
288 ms |
289100 KB |
Output is correct |
| 4 |
Correct |
287 ms |
289100 KB |
Output is correct |
| 5 |
Correct |
263 ms |
286328 KB |
Output is correct |
| 6 |
Correct |
188 ms |
261800 KB |
Output is correct |
| 7 |
Correct |
190 ms |
261580 KB |
Output is correct |
| 8 |
Correct |
187 ms |
261616 KB |
Output is correct |
| 9 |
Correct |
301 ms |
281084 KB |
Output is correct |
| 10 |
Correct |
307 ms |
281164 KB |
Output is correct |
| 11 |
Correct |
300 ms |
281072 KB |
Output is correct |
| 12 |
Correct |
296 ms |
280096 KB |
Output is correct |
| 13 |
Correct |
280 ms |
287308 KB |
Output is correct |
| 14 |
Incorrect |
189 ms |
261320 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
