帮一下兄弟帮一下 /kel

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')zf=0;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return (zf?x:-x);
}
void print(cint x)
{
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    print(x/10);
    putchar(x%10+'0');
}
void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint mod=1e9+7;
mt19937_64 mt(chrono::system_clock().now().time_since_epoch().count());
cint VN=1.6e6-2,N=8e5-1,M=4e5-1,Q=2e5,H=__lg(Q),SIZE=(N+Q)*(H+2)*2;
int pw[VN+1];
int n,m,q;
int cnt[Q+1];
struct Trie{
    struct node{
        int son[2],h;
        ull x;
    }t[SIZE+1];
    int tot;
    inline int copy(cint p,cint h)
    {
        t[++tot]=t[p];
        t[tot].h=h;
        return tot;
    }
    int rt[N+1];
    inline void insert(int p,cint x,cull y)
    {
        p=rt[p]=copy(rt[p],H+1);
        t[p].x^=y;
        for(int i=H;i>=0;--i)
        {
            const bool c=(x>>i&1);
            p=t[p].son[c]=copy(t[p].son[c],i);
            t[p].x^=y;
        }
    }
    int lcp(cint p,cint q)
    {
        if(t[p].x==t[q].x)return (1<<(t[p].h|t[q].h));
        if(!t[p].h&&!t[q].h)return 0;
        if(t[t[p].son[0]].x==t[t[q].son[0]].x)return (1<<(t[p].h|t[q].h)-1)+lcp(t[p].son[1],t[q].son[1]);
        return lcp(t[p].son[0],t[q].son[0]);
    }
    int merge(cint p,cint q)
    {
        if(!p||!q)return (p|q);
        cint r=copy(p,t[p].h);
        t[r].x^=t[q].x;
        t[r].son[0]=merge(t[p].son[0],t[q].son[0]);
        t[r].son[1]=merge(t[p].son[1],t[q].son[1]);
        return r;
    }
    inline void merge_into(cint p,cint q,cint r)
    {
        rt[r]=merge(rt[p],rt[q]);
    }
    vector<int>ver[H+2];
    int idx[SIZE+1],s[SIZE+1],tmp[SIZE+1];
    void base_sort(cint x)
    {
        int tr=0;
        for(int i=0;i<ver[x-1].size();++i)
        {
            if(!i||t[ver[x-1][i]].x!=t[ver[x-1][i-1]].x)++tr;
            idx[ver[x-1][i]]=tr;
        }
        idx[0]=!t[ver[x-1][0]].x;
        for(int i=0;i<=ver[x-1].size();++i)s[i]=0;
        for(int p:ver[x])++s[idx[t[p].son[1]]];
        for(int i=1;i<=ver[x-1].size();++i)s[i]+=s[i-1];
        for(int p:ver[x])tmp[s[idx[t[p].son[1]]]--]=p;
        for(int i=0;i<=ver[x-1].size();++i)s[i]=0;
        for(int p:ver[x])++s[idx[t[p].son[0]]];
        for(int i=1;i<=ver[x-1].size();++i)s[i]+=s[i-1];
        for(int i=ver[x].size();i>=1;--i)ver[x][--s[idx[t[tmp[i]].son[0]]]]=tmp[i];
    }
    void solve()
    {
        for(int i=1;i<=tot;++i)
        {
            ver[t[i].h].push_back(i);
        }
        sort(ver[0].begin(),ver[0].end(),[&](cint x,cint y){return (t[x].x==t[y].x?(x<y):(t[x].x<t[y].x));});
        for(int i=1;i<=H+1;++i)
        {
            base_sort(i);
        }
        for(int i=0;i<ver[H+1].size();++i)
        {
            idx[ver[H+1][i]]=i;
        }
        sort(rt+1,rt+n+1,[&](cint x,cint y){return (idx[x]<idx[y]);});
        for(int i=1;i<n;++i)
        {
            cint x=lcp(rt[i],rt[i+1]);
            if(x<q)++cnt[x];
        }
    }
}T;
int ls[M+1],rs[M+1];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read();
    q=read();
    m=(q<<1)-1;
    n=(q<<2)-1;
    for(int i=1;i<=m;++i)
    {
        ls[i]=read();
        rs[i]=read();
    }
    for(int i=1;i<=q;++i)
    {
        cint x=read(),y=read();
        cull v=mt();
        T.insert(x,i-1,v);
        T.insert(y,i-1,v);
    }
    for(int i=m;i>=1;--i)
    {
        T.merge_into(ls[i],rs[i],i);
    }
    T.solve();
    for(int i=1;i<=q;++i)
    {
        cnt[i]+=cnt[i-1];
    }
    pw[0]=1;
    for(int i=1;i<=VN;++i)
    {
        (pw[i]=pw[i-1]<<1)>=mod?(pw[i]-=mod):0;
    }
    for(int i=1;i<=q;++i)
    {
        princh(pw[m+i-cnt[i-1]],'\n');
    }
    return 0;
}