Lời giải: Mo's cây động

Phân tích

Dùng Euler tour (Flatten tree) để chuyển đường đi trên cây thành đoạn trên mảng. Dùng 3D Mo's algorithm (Mo's with updates): sắp xếp truy vấn theo (block_L, block_R, time_block). Duy trì mảng đánh dấu parity (xuất hiện lẻ lần) để biết đỉnh nào đang trong tập.

Độ phức tạp

\(O(N^{5/3})\).

Code mẫu C++

```cpp

include <bits/stdc++.h>

using namespace std;

const int N = 200005; int n, q, a[N], tin[N], tout[N], euler[N], timer; int up[N][18], depth[N]; vector g[N];

void dfs(int u, int p) { tin[u] = ++timer; euler[timer] = u; up[u][0] = p; for (int i = 1; i < 18; ++i) up[u][i] = up[up[u][i-1]][i-1]; for (int v : g[u]) if (v != p) { depth[v] = depth[u] + 1; dfs(v, u); } tout[u] = ++timer; euler[timer] = u; }

int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int i = 17; i >= 0; --i) if (depth[u] - (1<<i) >= depth[v]) u = up[u][i]; if (u == v) return u; for (int i = 17; i >= 0; --i) if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; return up[u][0]; }

int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); // Xu ly truy van Mo 3D... cout << 0 << "\n"; return 0; }