# Orange lecture #1 - Book of Evil

### 1, Đề bài
- n khu chỗ ở, n - 1 đường đi 2 chiều kết nối tất cả khu này -> cây vô hướng
- Book of Evil có phạm phi phá huỷ là d, các node bị ảnh hưởng là p[1], p[2], ..., p[m] -> tìm tất cả vị trí có khả năng đặt Book of Evil

Input:
- n, m, d
- p1, p2, ..., pm
- n - 1: dòng
+ u v

Output:
- Số lượng vị trí đặt Book of Evil

### 2, Ý tưởng & giải thuật
a) Bruteforce
- for u = 1 -> n: bfs(u)
check dist(u, p[1]) <= d && ... dist(u, p[m]) <= d
=> result += 1

=> O(N^2)

b) AC Solution
- Nhận xét:
+ Tìm cặp **s = p[i] - p[j] = r** xa nhau nhất trong số các node bị ảnh hưởng
+ Book of Evil gây ảnh hưởng tới cả 2 node này <=> Book Of Evil gây ảnh hưởng tới tất cả p[i]
**Chứng minh:**
Gọi t là vị trí đặt Book of Evil, s & r là cặp đỉnh bị ảnh hưởng xa nhau nhất, dist(t, s) <= d & dist(t, r) <= d
Giả sử tồn tại một đỉnh bị ảnh hưởng x mà dist(t, x) > d (*)
=> dist(s, x) = dist(s,t) + dist(t, x) > dist(s,t) + d >= dist(s, t) + dist(r, t) = dist(s, r) => (s, x) mới là cặp đỉnh bị ảnh hưởng xa nhau nhất, mẫu thuẫn với giả thiết (s, r) là cặp đỉnh bị ảnh hưởng xa nhau nhất => Mệnh đề (\*) bị bác bỏ

#### **Thuật toán:**
+ B1: Tìm cặp đỉnh đặc biệt/bị ảnh hưởng xa nhau nhất s, r
- Chọn 1 đỉnh p[j] bất kì -> tìm đỉnh bị ảnh hưởng cách xa p[j] nhất, gọi đỉnh này là q => ta khẳng định được: q hoặc là s hoặc là r (**)
- Từ s = q, tìm đỉnh bị ảnh hưởng xa nhất -> đỉnh đó là r
> **Chứng minh:**
> 
Giả sử q không là một trong 2 node bị ảnh hưởng cách xa nhau nhất. Ta dựng cây gốc p[j]:
Đặt p = lca(s, r) # lowest common ancestor
Đặt k = lca(s, r, q)
=> giả sử s là đỉnh có lca(s, q) = k # Chắc chắn một trong 2 đỉnh s, r khi lấy lca với q thì sẽ tạo ra k, ở đây ta giả sử nó là s
dist(s, r) = dist(s, p) + dist(p, r) <= dist(s, k) + dist(k, r)
<= dist(s, k) + [ dist(p[j], r) - dist(p[j], k) ] <= dist(s,k) + [dist(p[j], q) - dist(p[j], k)] = dist(s,k) + dist(q, k) = dist(s, q)
=> Như vậy q nằm trong cặp đỉnh bị ảnh hưởng cách xa nhau nhất -> mẫu thuẫn

=> Tóm lại: q LÀ một trong 2 node bị ảnh hưởng cách xa nhau nhất

- B2: Tìm tất cả các đỉnh có khoảng cách <= d đến hai đỉnh s,r -> Kết quả bài toán

### 3, Mã giả

graph[i] = {}
n, m, d = readInt(), readInt(), readInt()
p = readArrInt()
for i = 1 -> n - 1:
	u, v = readInt(), readInt()
  graph[u].add(v)
  graph[v].add(u)
    
#
x = p[0]
bfs(x)
q = -1 # find q
for i = 0 -> m - 1:
	if(q < 0 or dist(x, p[i]) > dist(x, q)):
      q = p[i]
      
s = q
#find r
bfs(s)
r = -1
for i = 0 -> m - 1:
	if(r < 0 or dist(s, p[i]) > dist(s, r)):
      r = p[i]

# s - r
# bfs(s)
bfs(r)

# find all vertices t | dist(s, t) <= d & dist(r, t) <= d
result = 0
for i = 1 -> n:
    if(dist(s, i) <= d & dist(r, i) <= d):
				result += 1
          
print(result)

### 4, Độ phức tạp
- **O(N)**