**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;
}
```
__+)Nếu độ dài đường đi từ u tới v là lẻ thì không có đáp án nào__
__+)Còn nếu là chẵn thì ta tính lên từ trung điểm x của u và v
có bao nhiêu cạnh tới được x mà không cần đi qua những điểm nằm trên
đoạn đường đi từ u tới v__
__*)Cách Làm bằng binary lifting **O(n log n + q log n)**__
- tìm $lca(u, v)$ rồi tìm độ dài đường đi từ u -> v
- gọi $ur, vr$ là 2 con gần x nhất chứa u và v
+ dùng binary lifting dễ dàng tìm $ur, vr$;
- $siz[i]$ là số lượng đỉnh trong cây con của đỉnh i (tính cả i)
- nếu $deep[u] = deep[v]$ điểm x chính là lca(u, v)
-> đáp án : $f(u, v) = n - (siz[ur] + siz[vr])$
- nếu deep[u] != deep[v] và ta định nghĩa deep[u] > deep[v]
-> đáp án : $f(u, v) = siz[x] - siz[ur]$
__AC CODE **O(n log n + q log n)**__
```cpp
#include <bits/stdc++.h>
#define id1 first
#define id2 second
#define fastIO ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
#define open_file(name) freopen(name".INP","r", stdin); freopen(name".OUT","w", stdout);
#define foru(i,index_begin,index_end) for (int i=index_begin;i<=index_end;i++)
#define ford(i,index_begin,index_end) for (int i=index_begin;i>=index_end;i--)
#define name "TENJOKE"
#define el '\n'
using namespace std;
const long long maxn = 1e5 + 9, mod = 1e9 + 7, inf = 1e18;
const int joker = 17;
int n, q, par[maxn][joker + 1], d[maxn], siz[maxn], ans[maxn];
vector<int> a[maxn];
void input()
{
cin >> n >> q;
foru(i,1,n - 1)
{
int x, y; cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void dfs_pre(int u, int p)
{
d[u] = d[p] + 1;
par[u][0] = p;
siz[u] = 1;
for (auto v : a[u])
{
if (v == p) continue;
dfs_pre(v, u);
siz[u] += siz[v];
}
}
void binary_liftting()
{
d[0] = -1; dfs_pre(1, 0);
foru(i,1,joker) foru(u,1,n) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
}
int lca(int u, int v)
{
if (d[v] > d[u]) swap(u, v);
ford(i,joker,0)
{
if (d[par[u][i]] >= d[v])
u = par[u][i];
}
if (u == v) return v;
ford(i,joker,0)
{
if (par[u][i] != par[v][i])
{
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
int cal(int u, int v)
{
int belan = lca(u, v), way;
way = d[u] + d[v] - d[belan] * 2;
if (way % 2 != 0) return 0;
if (d[u] == d[v])
{
ford(i,joker,0)
{
if (par[u][i] != par[v][i])
{
u = par[u][i];
v = par[v][i];
}
}
return n - (siz[u] + siz[v]);
}
if (d[v] > d[u]) swap(u, v);
way /= 2;
ford(i,joker,0)
{
if ((1 << i) < way)
{
way -= (1 << i);
u = par[u][i];
}
}
return siz[par[u][0]] - siz[u];
}
void s_p()
{
binary_liftting();
foru(i,1,q)
{
int u, v; cin >> u >> v;
ans[i] = cal(u, v);
}
}
void output()
{
foru(i,1,q) cout << ans[i] << el;
}
int main()
{
fastIO;
//open_file(name)
input();
s_p();
output();
return 0;
}
tuongll
Created at
21 likes
TENJOKE
Created at
0 likes