Solutions of Equal path - MarisaOJ: Marisa Online Judge

Solutions of Equal path

Select solution language

Write solution here.


User Avatar tuongll    Created at    11 likes

**Nhận xét:** Không tồn tại các đỉnh thỏa mãn khi và chỉ khi $f(u,v)$ là lẻ. Khi $f(u,v)$ chẵn, luôn tồn tại ít nhất một đỉnh thỏa mãn. **Chứng minh:** Giả sử $f(u,v)$ chẵn, gọi $c$ là đỉnh *chính giữa* trên đường đi từ $u$ đến $v$, dễ thấy $f(u,c)=f(c,v)=f(u,v)/2$, nên đỉnh $c$ thỏa mãn. Xét tập $S$ gồm các đỉnh $t$ tới được từ $c$ mà không đi qua các đỉnh thuộc đường đi từ $u$ đến $v$ (ngoại trừ $c$). Ta có $f(u,t)=f(u,c)+f(c,t)$ và $f(v,t)=f(v,c)+f(c,t)$, suy ra $f(u,t)=f(v,t)$, và các đỉnh này cũng thỏa mãn. Ta chứng minh tiếp rằng không còn đỉnh nào khác thỏa mãn. Ta xét hai trường hợp: 1. Xét các đỉnh $x$ trên đường đi từ $u$ đến $v$, khác $c$. Khi $x$ thuộc đoạn từ $u$ đến $c$ thì $f(u,x)<f(x,v)$, còn khi $x$ thuộc đoạn từ $c$ đến $v$ thì $f(u,x)>f(x,v)$, nên các đỉnh này không thoả mãn. 2. Xét các đỉnh $x$ mà chỉ có thể tới được từ $c$ bằng cách đi qua ít nhất một đỉnh thuộc đường đi từ $u$ đến $v$ (ngoại trừ $c$). Ta cũng chứng minh được rằng các đỉnh này không thỏa mãn, tương tự với cách chứng minh các đỉnh thuộc $S$ thỏa mãn. Khi $f(u,v)$ lẻ, không tồn tại đỉnh $c$ chính giữa, từ đó suy ra không có đỉnh nào khác thỏa mãn. Vậy ta có điều phải chứng minh. ### Thuật toán Trong phần chứng minh, ta biết rằng ta chỉ cần tìm đỉnh $c$ và các đỉnh thuộc $S$. Không mất tính tổng quát, giả sử $f(1,u)\le f(1,v)$ (ta có thể hoán đổi $u$ và $v$ để chắc chắn điều kiện này được thỏa mãn), đồng thời $f(u,v)$ chẵn. Ký hiệu $s_u$ là số đỉnh thuộc cây con gốc $u$ (chọn gốc của cây là $1$). Xét ba trường hợp sau: 1. $u$ là tổ tiên của $v$ (hay $lca(u,v)=u$): suy ra $u$ cũng là tổ tiên của $c$. Ký hiệu $r_v$ là con của $c$ mà cây con gốc nó chứa $v$. Thấy rằng các đỉnh *không thuộc* cây con gốc $c$ sẽ không thỏa mãn, đồng thời các đỉnh *thuộc* cây con gốc $r_v$ cũng không thỏa mãn. Suy ra đáp án là $s_c-s_{r_v}$. 2. $f(1,u)=f(1,v)$, suy ra $lca(u,v)=c$: định nghĩa $r_u$ tương tự $r_v$ như trên. Khi này, các đỉnh không thỏa mãn là các đỉnh thuộc cây con gốc $r_u$ và $r_v$, vậy đáp án là $s_1-(s_{r_u}+s_{r_v})$. 3. Không có điều kiện đặc biệt: dễ thấy các đỉnh không thuộc cây con gốc $c$ không thỏa mãn, và các đỉnh thuộc cây con gốc $r_v$ cũng không thỏa mãn, tức đáp án giống trong trường hợp 1. Ta có thể tính trước các giá trị $s_u$ và $f(1,u)$ bằng một lượt DFS từ đỉnh $1$ trong $O(n)$. Với mỗi truy vấn, ta cần phải tính $f(u,v)$ và tìm các đỉnh liên quan. Vậy tổng độ phức tạp của thuật toán là $O(n \log n + q \log n)$. Code mẫu: ```cpp #include <bits/stdc++.h> #define ll long long #define debug(x) cout << #x << " = " << x << '\n' #define all(a) a.begin(), a.end() using namespace std; const int mxn = 1e5 + 3; const ll mod = 1e9 + 7; const int inf32 = 2e9; const ll inf64 = 7e18; int n, q; vector<int> g[mxn]; int up[mxn][18], h[mxn], sz[mxn]; void dfs(int u, int pre){ sz[u] = 1; for (int v : g[u]) if (v != pre){ h[v] = h[u] + 1; up[v][0] = u; dfs(v, u); sz[u] += sz[v]; } } int anc(int u, int k){ for (int j = 0; (1 << j) <= k; ++j) if (k >> j & 1) u = up[u][j]; return u; } int lca(int u, int v){ if (h[u] != h[v]){ if (h[u] < h[v]) swap(u, v); u = anc(u, h[u] - h[v]); } if (u == v) return u; for (int j = log2(h[u]); j >= 0; --j){ if (up[u][j] != up[v][j]) u = up[u][j], v = up[v][j]; } return up[u][0]; } void solve(){ cin >> n >> q; for (int i = 1, u, v; i <= n - 1; ++i){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); for (int j = 1; j < 18; ++j){ for (int u = 1; u <= n; ++u){ up[u][j] = up[up[u][j - 1]][j - 1]; } } while(q--){ int u, v; cin >> u >> v; int k = lca(u, v); int len = h[u] + h[v] - 2 * h[k]; if (len & 1){ cout << 0 << '\n'; continue; } if (h[u] > h[v]) swap(u, v); int r_v = anc(v, len / 2 - 1); int mid = up[r_v][0]; if (h[u] == h[v]){ int r_u = anc(u, len / 2 - 1); cout << sz[1] - sz[r_u] - sz[r_v] << '\n'; } else cout << sz[mid] - sz[r_v] << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; } ```