[日常训练]Hard（组合数学 + FMT）

Meaning

• 有一棵 n n n 个点的树，根结点为 1 1 1 号结点，初始时每个结点有一个值 a i a_i ai​
• 每一轮，你需要从根结点开始，将每个结点的权值更新为它子树中所有结点上一轮结束后权值的异或和
• 有 q q q 个询问，每个询问给定轮数 T T T ，你需要输出 T T T 轮后根结点的值
• 0 ≤ T , a i ≤ 1 0 18 , 1 ≤ n , q ≤ 1 0 6 0\le T,a_i\le10^{18},1\le n,q\le10^6 0≤T,ai​≤1018,1≤n,q≤106

Solution

• 好题
• 先特判掉 T = 0 T=0 T=0
• 可以发现 T T T 轮操作之后根节点的值的组合意义
• 即对于一个点 u u u ，如果从点 u u u 开始，跳 T T T 步（每步只能跳向自己及其祖先）到达根的方案数为奇数，则 a u a_u au​ 为答案以异或的方式贡献，否则不贡献
• 这个组合意义可以通过归纳等手段得出
• 根据组合数学插板法，我们易得点 u u u 跳 T T T 步跳到根的方案数为 ( d e p u + T − 1 T − 1 ) \binom{dep_u+T-1}{T-1} (T−1depu​+T−1​) （ d e p u dep_u depu​ 为点 u u u 的深度，根的深度为 0 0 0 ）
• 根据 Lucas 定理，我们可以判断 ( a b ) \binom ab (ba​) 的奇偶性
• 即对于任何一个 i i i ，都不满足「 a a a 的第 i i i 个二进制位为 0 0 0 且 b b b 的第 i i i 个二进制位为 1 1 1」
• 即二进制意义下， b b b 为 1 1 1 的位是 a a a 为 1 1 1 的位的子集
• 我们继续研究 ( d e p u + T − 1 T − 1 ) ≡ 1 (   m o d   2 ) \binom{dep_u+T-1}{T-1}\equiv1(\bmod 2) (T−1depu​+T−1​)≡1(mod2) 的条件
• 即 T − 1 T-1 T−1 中为 1 1 1 的位是 d e p u + T − 1 dep_u+T-1 depu​+T−1 中为 1 1 1 的位的子集的条件
• 容易发现，如果我们能够找到一个最低的位 i i i 满足 T − 1 T-1 T−1 的第 i i i 位和 d e p u dep_u depu​ 的第 i i i 位都为 1 1 1 ，那么 d e p u + T − 1 dep_u+T-1 depu​+T−1 的第 i i i 位必然因为进位而变成 0 0 0 ，这时候显然就不满足条件了
• 于是 T − 1 T-1 T−1 中为 1 1 1 的位是 d e p u + T − 1 dep_u+T-1 depu​+T−1 中为 1 1 1 的位的子集，当且仅当 T − 1 T-1 T−1 中为 1 1 1 的位与 d e p u dep_u depu​ 中为 1 1 1 的位没有交集
• 即 d e p u dep_u depu​ 是 T − 1 T-1 T−1 的补集的子集
• 设 s u m i sum_i sumi​ 表示深度为 i i i 的点的权值异或和
• 那么一次询问相当于求
• ⨁ i ⊂ S s u m i \bigoplus_{i\subset S}sum_i i⊂S⨁​sumi​
• S S S 表示 T − 1 T-1 T−1 各位取反之后得到的数， i ⊂ S i\subset S i⊂S 表示 i i i 中为 1 1 1 的位是 S S S 中为 1 1 1 的位的子集
• 可以用 FMT O ( n log ⁡ n ) O(n\log n) O(nlogn) 预处理后 O ( 1 ) O(1) O(1) 回答
• O ( n log ⁡ n + q ) O(n\log n+q) O(nlogn+q)

Code

#include <bits/stdc++.h>

// 0830

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

typedef long long ll;

inline ll readll()
{
	ll res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

const int N = 11e5 + 5, M = N << 1;

int n, q, ecnt, nxt[M], adj[N], go[M], ff = 1, tot;
ll T, a[N], sum[N];

void add_edge(int u, int v)
{
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}

void dfs(int u, int dep, int fu)
{
	sum[dep] ^= a[u];
	for (int e = adj[u], v; e; e = nxt[e])
		if ((v = go[e]) != fu) dfs(v, dep + 1, u);
}

int main()
{
	#ifdef orzInvUsr
	#else
		freopen("hard.in", "r", stdin);
		freopen("hard.out", "w", stdout);
	#endif
	
	int x, y;
	n = read(); q = read();
	for (int i = 1; i < n; i++)
		x = read(), y = read(), add_edge(x, y);
	for (int i = 1; i <= n; i++) a[i] = readll();
	dfs(1, 0, 0);
	while (ff < n) ff <<= 1, tot++;
	for (int i = 0; i < tot; i++)
		for (int j = 0; j < ff; j += (1 << i + 1))
			for (int k = 0; k < (1 << i); k++)
				sum[j + (1 << i) + k] ^= sum[j + k];
	while (q--)
	{
		T = read();
		if (!T) {printf("%lld\n", a[1]); continue;}
		T--;
		printf("%lld\n", sum[ff - 1 ^ (T & ff - 1)]);
	}
	return 0;
}