**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;
}
```
tuongll
Created at
7 likes