#include<bits/stdc++.h>
using namespace std;
struct node{
long long countz,tag,res;
set<pair<long long ,long long>>mn;
node(){
countz=res=1;
tag=0;
};
};
vector<long long>high;
long long mod=1e9+7;
vector<long long>fact,revfact;
long long n,r;
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)==1){
p=1ll*m*p;
p%=mod;
}
return p;
}
vector<long long>st;
vector<pair<long long ,long long>>stf;
vector<vector<long long>>adj;
long long rishe=1;
node seg[(1<<20)];
void build(long long i){
if((i<<1)>=(1<<20)){
return ;
}
build((i<<1));
build(((i<<1)^1));
seg[i].countz=seg[(i<<1)].countz+seg[((i<<1)^1)].countz;
}
void aval(long long u=rishe,long long para=0,long long len=0){
high[u]=len;
st.push_back(u);
stf[u].first=st.size()-1;
for(auto x:adj[u]){
if(x!=para){
aval(x,u,len+1);
}
}
stf[u].second=st.size()-1;
}
long long solvecz(long long i,long long nl,long long nr,long long tl,long long tr){
if(nl>tr||nr<tl){
return 0;
}
if(nl>=tl&&nr<=tr){
// cout<<nl<<" asd "<<nr<<" "<<seg[i].countz<<"\n";
return seg[i].countz;
}
long long m=((nl+nr)>>1);
long long d=solvecz((i<<1),nl,m,tl,tr);
d+=solvecz(((i<<1)^1),m+1,nr,tl,tr);
return d;
}
long long solvest(long long i,long long nl,long long nr,long long tl,long long tr){
if(nl>tr||nr<tl){
return 0;
}
if(nl>=tl&&nr<=tr){
// cout<<nl<<" asd "<<nr<<" "<<seg[i].tag<<"\n";
return seg[i].tag;
}
long long m=((nl+nr)>>1);
long long d=solvest((i<<1),nl,m,tl,tr);
d+=solvest(((i<<1)^1),m+1,nr,tl,tr);
return d;
}
void upmn(long long i,long long nl,long long nr,long long tl,long long tr,long long u){
if(nl>tr||nr<tl){
return ;
}
if(nl>=tl&&nr<=tr){
seg[i].mn.insert(make_pair(-high[u],u));
return ;
}
long long m=((nl+nr)>>1);
upmn((i<<1),nl,m,tl,tr,u);
upmn(((i<<1)^1),m+1,nr,tl,tr,u);
return ;
}
void upd(long long u){
if(u==0){
return ;
}
seg[u].res=seg[(u<<1)].res*seg[((u<<1)^1)].res;
seg[u].res%=mod;
seg[u].countz=seg[(u<<1)].countz+seg[((u<<1)^1)].countz;
seg[u].tag=seg[(u<<1)].tag+seg[((u<<1)^1)].tag;
return upd((u>>1));
}
long long solvepar(long long u){
if(u==0){
return -1;
}
long long x=solvepar((u>>1));
if(x==-1){
if(seg[u].mn.size()==0){
return -1;
}
pair<long long,long long> y=*(seg[u].mn.begin());
return y.second;
}
else{
if(seg[u].mn.size()==0){
return x;
}
pair<long long,long long> y=*(seg[u].mn.begin());
if(high[x]>-y.first){
return x;
}
else{
return y.second;
}
}
}
void update(long long u,long long no,long long c=0){
if(no==1){
if(stf[u].first==stf[u].second){
seg[(1<<19)+stf[u].first].tag=c;
seg[(1<<19)+stf[u].first].res=1;
seg[(1<<19)+stf[u].first].countz=0;
}
else{
upmn(1,0,(1<<19)-1,stf[u].first+1,stf[u].second,u);
seg[(1<<19)+stf[u].first].tag=c;
seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
if(x>c){
seg[(1<<19)+stf[u].first].res=0;
}
else{
seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
seg[(1<<19)+stf[u].first].res%=mod;
seg[(1<<19)+stf[u].first].res*=revfact[c-x];
seg[(1<<19)+stf[u].first].res%=mod;
}
// cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
}
long long fu=stf[u].first,ffu=u;
fu+=(1<<19);
fu=(fu>>1);
upd(fu);
fu=stf[u].first;
fu+=(1<<19);
u=solvepar(fu);
fu=ffu;
if(u==-1){
return ;
}
seg[(1<<19)+stf[u].first].tag-=seg[(1<<19)+stf[fu].first].tag;
c=seg[(1<<19)+stf[u].first].tag;
// cout<<" s "<<u<<"\n";
if(stf[u].first==stf[u].second){
seg[(1<<19)+stf[u].first].res=1;
seg[(1<<19)+stf[u].first].countz=0;
}
else{
seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
if(x>c){
seg[(1<<19)+stf[u].first].res=0;
// cout<<c<<" "<<x<<"\n";
}
else{
seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
seg[(1<<19)+stf[u].first].res%=mod;
seg[(1<<19)+stf[u].first].res*=revfact[c-x];
seg[(1<<19)+stf[u].first].res%=mod;
}
// cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
}
fu=stf[u].first;
fu+=(1<<19);
fu=(fu>>1);
upd(fu);
}
else{
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fact.resize(1e6);
revfact.resize(1e6);
fact[0]=revfact[0]=1;
for(int i=1;i<=5e5;i++){
fact[i]=fact[i-1]*i;
fact[i]%=mod;
revfact[i]=mypow(fact[i],mod-2);
}
cin>>n>>r;
adj.resize(n+1);
high.resize(n+1);
stf.resize(n+1);
for(int i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
build(1);
aval();
update(1,1,r);
long long q;
cin>>q;
cout<<seg[1].res<<"\n";
for(int i=0;i<q;i++){
long long u;
cin>>u;
if(u==1){
long long v,e;
cin>>v>>e;
update(v,1,e);
}
else{
}
cout<<seg[1].res<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
114428 KB |
Output is correct |
| 2 |
Correct |
345 ms |
114492 KB |
Output is correct |
| 3 |
Correct |
352 ms |
114532 KB |
Output is correct |
| 4 |
Correct |
351 ms |
114540 KB |
Output is correct |
| 5 |
Correct |
340 ms |
110912 KB |
Output is correct |
| 6 |
Correct |
252 ms |
90220 KB |
Output is correct |
| 7 |
Correct |
253 ms |
90096 KB |
Output is correct |
| 8 |
Correct |
242 ms |
90112 KB |
Output is correct |
| 9 |
Correct |
345 ms |
108908 KB |
Output is correct |
| 10 |
Correct |
355 ms |
108840 KB |
Output is correct |
| 11 |
Correct |
345 ms |
108900 KB |
Output is correct |
| 12 |
Correct |
340 ms |
108060 KB |
Output is correct |
| 13 |
Correct |
329 ms |
112868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
89812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
393 ms |
117084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
500 ms |
112932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
114428 KB |
Output is correct |
| 2 |
Correct |
345 ms |
114492 KB |
Output is correct |
| 3 |
Correct |
352 ms |
114532 KB |
Output is correct |
| 4 |
Correct |
351 ms |
114540 KB |
Output is correct |
| 5 |
Correct |
340 ms |
110912 KB |
Output is correct |
| 6 |
Correct |
252 ms |
90220 KB |
Output is correct |
| 7 |
Correct |
253 ms |
90096 KB |
Output is correct |
| 8 |
Correct |
242 ms |
90112 KB |
Output is correct |
| 9 |
Correct |
345 ms |
108908 KB |
Output is correct |
| 10 |
Correct |
355 ms |
108840 KB |
Output is correct |
| 11 |
Correct |
345 ms |
108900 KB |
Output is correct |
| 12 |
Correct |
340 ms |
108060 KB |
Output is correct |
| 13 |
Correct |
329 ms |
112868 KB |
Output is correct |
| 14 |
Incorrect |
240 ms |
89812 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
