题解

#include<bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N=8e5+10,mod=1e9+7;
typedef unsigned long long ll;
int ID,n,ls[N],rs[N],pw[N];
vector<int>tr[N];
mt19937_64 rnd(chronosteady_clocknow().time_since_epoch().count());
int rt[N],idx;
struct node{
int ls,rs;
ll tag;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define tag(x) tree[x].tag
}tree[N40];
inline void push_up(int now){
tag(now)=(tag(ls(now))^tag(rs(now)));
}
inline void insert(int &now,int l,int r,int pos,ll num){
if(!now){
now=++idx;
}
if(lr){
tag(now)^=num;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
insert(ls(now),l,mid,pos,num);
}else{
insert(rs(now),mid+1,r,pos,num);
}
push_up(now);
}
inline int merge(int nx,int ny,int l,int r){
if(!nx || !ny){
return nx+ny;
}
int now=++idx;
tag(now)=(tag(nx)^tag(ny));
if(lr){
return now;
}
int mid=(l+r)>>1;
ls(now)=merge(ls(nx),ls(ny),l,mid);
rs(now)=merge(rs(nx),rs(ny),mid+1,r);
return now;
}
inline int compare(int nx,int ny,int l,int r){
if(tag(nx)tag(ny)){
return r;
}
if(lr){
return 0;
}
int mid=(l+r)>>1;
int ln=compare(ls(nx),ls(ny),l,mid);
if(lnmid){
int cur=compare(rs(nx),rs(ny),mid+1,r);
if(cur!=0){
return cur;
}
return mid;
}
return ln;
}
inline ll query(int now,int l,int r,int L,int R){
if(L<=l && r<=R){
return tag(now);
}
int mid=(l+r)>>1;
if(R<=mid){
return query(ls(now),l,mid,L,R);
}else if(mid<L){
return query(rs(now),mid+1,r,L,R);
}else{
return(query(ls(now),l,mid,L,R)^query(rs(now),mid+1,r,L,R));
}
}
inline bool check(int now,int p){
return(query(rt[now],1,n,p,p)!=0);
}
inline int lcp(int x,int y){
return compare(rt[x],rt[y],1,n);
}
inline bool get(int nx,int ny,int l,int r){
if(lr){
if(tag(nx)==tag(ny)){
return false;
}
return(tag(nx)==0);
}
int mid=(l+r)>>1;
if(tag(ls(nx))==tag(ls(ny))){
return get(rs(nx),rs(ny),mid+1,r);
}else{
return get(ls(nx),ls(ny),l,mid);
}
}
inline bool cmp(int x,int y){
return get(rt[x],rt[y],1,n);
}
int id[N2],w[N];
inline void work(int pos){
for(int to:tr[pos]){
work(to);
rt[pos]=merge(rt[pos],rt[to],1,n);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>ID>>n;
pw[0]=1;
for(int i=1;i<=4n;++i){
pw[i]=pw[i-1]2%mod;
}
for(int i=1;i<=2n-1;++i){
cin>>ls[i]>>rs[i];
tr[i].push_back(ls[i]);
tr[i].push_back(rs[i]);
}
for(int i=1;i<=n;++i){
int x,y;
cin>>x>>y;
ll cur=rnd();
insert(rt[x],1,n,i,cur);
insert(rt[y],1,n,i,cur);
}
work(1);
for(int i=1;i<=4n-1;++i){
id[i]=i;
}
sort(id+1,id+(4n-1)+1,cmp);
for(int i=1;i<4n-1;++i){
++w[lcp(id[i],id[i+1])+1];
}
w[0]=1;
for(int i=1;i<=n;++i){
w[i]+=w[i-1];
}
for(int i=1;i<=n;++i){
cout<<pw[2*n-1-w[i]+(i+1)]<<'\n';
}
return 0;
}