树上求值 tree

考场上想不出t2，于是把t3写了，感觉比较板。

思路：

暴力很显然，直接枚举每个点，暴力计算，复杂度\(O(Tn^2log_n)\) 。

看到贡献与 \(\operatorname{lca}\) 相关，想到在 \(\operatorname{lca}\) 处统计贡献。

显然，一个点 \(x\) 的答案可以分为两类：

1. \(x\) 子树内的点 \(i\) 对 \(x\) 的贡献，这时 \(\operatorname{lca}(x,i)=x\) ，记该贡献为 \(f_x\) 。
2. \(x\) 子树外的点 \(i\) 对 \(x\) 的贡献，记该贡献为 \(g_x\) 。

看到这个形式，显然是换根dp。假设已求出 \(f_x\) ，考虑 \(g_x\) 如何求：

对于 \(A\) 部分的点 \(i\)，有 \(\operatorname{lca}(x,i)=\operatorname{lca}(fa,i)\) ，于是它们的贡献为 \(g_{fa}\) 。

对于 \(B\) 部分的点 \(j\) ，有 \(\operatorname{lca}(x,j)=fa\) ，即让 \(f_{fa}\) 减去 \(x\) 子树的贡献即可。

于是问题转化为求 \(f_x\) 。让我们把 \(f_x\) 写出来：

\[f_x=\sum _{i} f(i+d_x) \]

直接暴力求显然不行，考虑从儿子处转移。令 \(v\) 为 \(x\) 的儿子，则：

\[\sum f_v=\sum f(i+d_v)=\sum f(i+d_x+1) \]

我们需要将所有 \(f(x)\) 变为 \(f(x-1)\) 。联系到 \(f(x)\) 的值与二进制位相关，想到 01trie。

我们需要用 01trie 维护以下操作：

1. 插入一个数
2. 将儿子合并到父亲的 01trie 上
3. 将整个 01trie 的值减一。

并需要时时维护 01trie 上所有值的 \(\sum f(i)\) 。

假设 01trie 上有一些数\(a_1,a_2 \dots a_n\) ，这些数在二进制前 \(k\) 位都是一样的，即前 \(k\) 位在 01trie 上是重合的。有：

\[\sum f(a_i)=\sum_i \prod_j A(b_{i,j})_j=\prod_{j=0}^kA(b_j)_j\sum_i\prod_{j=k+1}^{20}A(b_{i,j})_j \]

即可以用乘法分配律将拥有相同前缀的点的贡献拆开。因此我们可以记 \(val_i\) 表示在 01trie 上点 \(i\) 所在的位数后所有位的贡献，具体的，若 \(i\) 的深度为 \(d\) ，则\(val_i=\sum\prod_{j=d}^{20}A(b_{x,j})_j\) 。

则有 \(val_i=val_{ls}\times A(0)_d+val_{rs}\times A(1)_d\) ，若 \(i\) 是叶子则 \(val_i=siz_i\) 。

然后操作 \(1\) 直接加点，操作 \(2\) 使用 01trie 合并，这些操作都是平凡的。

对于操作 \(3\) ，这是一个经典的trick ，有两道例题 P6623 [省选联考 2020 A 卷] 树 P6018 [Ynoi2010] Fusion tree

要实现 01trie 上所有值减一的操作，考虑一个数减一后的变化：

\[3(11)_2-1=2(10)_2\\6(110)_2-1=5(101)_2\\12(1100)_2-1=11(1001)_2\\64(1000000)_2-1=63(0111111)_2 \]

发现什么规律了吗？一个数减一相当于将其二进制中第一个 \(1\)变成 \(0\)，其前所有 \(0\) 变成 \(1\) 。体现到 trie 数上，就是找到全是 \(0\) 的链，从下向上交换左右儿子。

当然，这时 01trie 需要从低位向高位建树。

这里以 \({4,5,6}\) 为例：

在操作途中，类似线段树，时时up即可。时间复杂度就是深度 \(O(\log n)\)

这样，每次合并儿子、全体减一，时时维护 \(val\) ，即可算出 \(f_i\) 。

实现细节：

在处理换根时，需要减去 \(x\) 自己所在子树的贡献，即 \(\sum f(i+d_{fa})\) ，记 \(h_i\) 为该值，就是将 \(f_i\) 计算后进行一次减一操作后的值，帮助转移。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,K=23,inf=1e18;int read(){int ans=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())ans=(ans<<1)+(ans<<3)+(c^48);return f?-ans:ans;
}void print(int x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10|48);
}int n,P,h[N],root,rt[N],d[N],f[N],f2[N],ans[N],val[N],a[2][K];//f2为上述h
struct edge{int nxt,to;
}e[N<<1];void adde(int u,int v){static int i=0;e[++i]={h[u],v};h[u]=i;
}namespace trie{//01trie维护f函数的值int t[N*K][2],siz[N*K],f[N*K],tot;//此处f为上述valint newnode(){++tot;t[tot][0]=t[tot][1]=siz[tot]=f[tot]=0;return tot;}void up(int p,int d){f[p]=(f[t[p][0]]*a[0][d]+f[t[p][1]]*a[1][d])%P;}void insert(int &p,int d,int x){if(!p)p=newnode();++siz[p];if(d==21){f[p]=siz[p];return;}insert(t[p][(x>>d)&1],d+1,x);up(p,d);}int merge(int x,int y,int d){if(!x||!y)return x+y;if(d==21)return siz[x]+=siz[y],f[x]=siz[x],x;t[x][0]=merge(t[x][0],t[y][0],d+1);t[x][1]=merge(t[x][1],t[y][1],d+1);return up(x,d),x;}void change(int x,int d){if(!x||d==21)return;swap(t[x][0],t[x][1]);change(t[x][1],d+1);up(x,d);}
}void dfs1(int u,int fa){//求出fd[u]=d[fa]+1;trie::insert(rt[u],0,u+d[u]);val[u]=trie::f[rt[u]];for(int i=h[u],v;i;i=e[i].nxt){v=e[i].to;if(v==fa)continue;dfs1(v,u);rt[u]=trie::merge(rt[u],rt[v],0);}f[u]=trie::f[rt[u]];trie::change(rt[u],0);f2[u]=trie::f[rt[u]];
}void dfs2(int u,int fa,int fw){//此处fw为上述g,因为不需要记录就当作参数传下来。ans[u]=(f[u]+fw)%P;rt[u]=0;for(int i=h[u],v;i;i=e[i].nxt){v=e[i].to;if(v==fa)continue;int nfw=(fw+f[u]-f2[v]+P)%P;dfs2(v,u,nfw);}
}signed main(){n=read();for(int i=1,u,v;i<n;++i){u=read();v=read();adde(u,v);adde(v,u);}int T=read();while(T--){root=read();P=read();for(int i=0;i<=20;++i)a[0][i]=read();for(int i=0;i<=20;++i)a[1][i]=read();trie::tot=0;dfs1(root,0);dfs2(root,0,0);int an=0;for(int i=1;i<=n;++i)an^=(i*ans[i]);print(an);putchar('\n');}return 0;
}