Code Level: ※
Thinking Level: ※※※

Description

一棵树，根编号1，原始带权，到第i+1天变为第i天子树节点的异或和。
求第x天根编号

$n, q ≤ 200000;\ \ \ Ai, x ≤ 10^{18}$

Solution

对于一棵树，子树节点对根节点的贡献只与其深度有关
进一步,第i天深度为j的子节点对根的贡献为第i-1天所有子树对根节点的贡献（第i-1天所有子树关深度于j节点的系数在第i天叠加），即

$d_{i,j}=\sum_{k=0}^{k<=j}{d_{i-1,k}}$

(定义根节点深度为0，是为了方便式子的转化)
发现每一步递推决策为当前步选[0,j]和上一步组成j的方案数
则此递推式的含义可为，i个未知数（可以为零）和为j的方案数
故可直接得出

$d_{i,j}=C_{i+j-1}^{j-1}\ \ \ (隔板法)$

而又因为贡献是异或和，所以只关心系数的奇偶性
即当且只当此时系数为奇时，此深度节点会对根节点造成贡献
即关心

$(_m^n) mod \ 2==1$

根据Lucas定理：

$(_m^n) mod \ 2=(_{m\ mod\ 2}^{n\ mod\ 2})*(_{m/2}^{n/2})$

而又

$C(1,0)=C(1,1)=C(0,0)=1且C(0,1)不存在$

可知条件满足的充分必要条件是：n&m==m
(m/2，n/2可以理解为它们整体二进制右移，则Lucas定理则是在比较它们的每一个二进制位)

所以我们得到，当 n+m-1&n-1=n-1 深度m的点会在第n天造成贡献
即当 n-1&m=0

而关注此式的取值范围，它很明显是通过不同深度是否贡献来得到不同取值
所以当

$2^k>max_{deep}时，天数x的ans=天数x\ mod\ max_{deep}的ans$

而n-1&m=0的情况完全可以直接枚举n-1的满足条件的子集m去构成答案
则最后答案也就等于

$ans[((n-1)\ mod \ 2^k\ \ xor\ (2^k-1))]$

最后一步就是取

$(n-1)\ mod\ 2^k关于域2^k的补$

Code

#include<bits/stdc++.h>
using namespace std;
const int nn=200005;
typedef long long ll;
int n,q,mx,tot=0,lg=1,f[nn];ll a[nn],dep[nn],ans[1<<19];
struct alp{
    int t,n;
}e[nn*2];
void ade(int x,int y){e[++tot]=(alp){y,f[x]};f[x]=tot;}
void run(int now,int pre,int deep){
    for(int i=f[now];i;i=e[i].n){
        int to=e[i].t; if(to==pre) continue ;
        run(to,now,deep+1);
    } dep[deep]^=a[now]; mx=max(mx,deep);
}
void rl(ll &x){
    x=0; char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar()) x=x*10-'0'+c;
}
int main(){
    int j,i,x,y,pr; scanf("%d%d",&n,&q);
    for(i=1;i<n;i++){ scanf("%d%d",&x,&y); ++x;++y; ade(x,y); ade(y,x); } 
    for(i=1;i<=n;i++) rl(a[i]);
    run(1,0,0); mx++;  while(lg<mx) lg<<=1;
    for(i=0;i<mx;i++){
        pr=(lg-1)^i;
        for(j=pr;j;j=(j-1)&pr) ans[i+j]^=dep[i];
        ans[i]^=dep[i]; 
    } 
    ll xx;
    for(i=1;i<=q;i++){ rl(xx); xx=(xx-1)%lg;  printf("%lld\n",ans[xx^(lg-1)]); }
    return 0;
}