求助

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef unsigned int ui;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=2e5+10;

ll fa[N],ans[N],s[N],dep[N],rt[N],a[N],b[N],c[32],n,T,rot,mod;
vector<int> e[N];
struct Trie
{
    struct P{int son[2],d;ll val;}tree[N*32];
    int tot=0;
    inline void clear()
    {
        for(int i=1;i<=tot;i++) tree[i]=tree[0];
        tot=0;
    }
    inline void pushup(int p)
    {
        tree[p].val=(tree[tree[p].son[0]].val*a[tree[p].d]%mod+tree[tree[p].son[1]].val*b[tree[p].d]%mod)%mod;
    }
    inline void insert(int p,int x)
    {
        c[0]=p;
        for(int i=0;i<=20;i++)
        {
            int t=((x>>i)&1);
            if(tree[p].son[t]==0)
            {
                tree[p].son[t]=++tot;
                tree[tot].d=i+1;
            }
            p=tree[p].son[t];
            c[i+1]=p;
        }
        tree[p].val++;
        for(int i=20;i>=0;i--) pushup(c[i]);
    }
    inline void change(int p)
    {
        c[0]=p;
        int siz=0;
        while(c[siz])
        {
            swap(tree[c[siz]].son[0],tree[c[siz]].son[1]);
            c[++siz]=tree[c[siz]].son[1];
        }
        for(int i=siz-1;i>=0;i--) pushup(c[i]);
    }
    inline int merge(int p1,int p2)
    {
        if(p1==0) return p2;
        if(p2==0) return p1;
        tree[p1].son[0]=merge(tree[p1].son[0],tree[p2].son[0]);
        tree[p1].son[1]=merge(tree[p1].son[1],tree[p2].son[1]);
        pushup(p1);
        return p1;
    }
}trie;

void dfs1(int u)
{
    trie.insert(rt[u],u+dep[u]);
    for(int v:e[u])
    {
        if(v!=fa[u])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            trie.change(rt[v]);
            s[v]=trie.tree[rt[v]].val;
            rt[u]=trie.merge(rt[u],rt[v]);
        }
    }
    ans[u]=trie.tree[rt[u]].val;
}

void dfs2(int u,ll sum)
{
    sum=(sum+ans[u])%mod;
    ans[u]=sum;
    for(int v:e[u]) if(v!=fa[u]) dfs2(v,(sum-s[v]+mod)%mod);
}

inline int read()
{
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9')
    {
        k=(k<<1)+(k<<3)+ch-'0';
        ch=getchar();
    }
    return k;
}

int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin >> T;
    while(T--)
    {
        cin >> rot >> mod;
        for(int i=0;i<=20;i++) a[i]=read();
        for(int i=0;i<=20;i++) b[i]=read();
        trie.clear();
        memset(fa,0,sizeof(fa));
        memset(ans,0,sizeof(ans));
        memset(s,0,sizeof(s));
        memset(dep,0,sizeof(dep));
        memset(rt,0,sizeof(rt));
        for(int i=1;i<=n;i++)
        {
            rt[i]=++trie.tot;
            trie.tree[rt[i]].d=0;
        }
        dep[rot]=1;
        dfs1(rot);
        dfs2(rot,0);
        ll sum=0;
        for(int i=1;i<=n;i++) sum^=(i*ans[i]);
        cout << sum << '\n';
    }
    return 0;
}