[日常訓練]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;
}