Hướng dẫn giải của Bedao Regular Contest 02 - TOURIST
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Ta dựng cây gốc ~A~, gọi các đỉnh trên đường đi từ ~A~ đến ~B~ lần lượt là ~u_1~, ~u_2~, ~\dots~ , ~u_k~
Ta thấy đáp án tối ưu sẽ có đường đi của ~A~ là từ ~A~ đến ~u_i~, rồi đi tiếp xuống một nhánh khác nhánh chứa đỉnh ~B~ và nhánh đó chứa nút lá có độ sâu lớn nhất trong số các nhánh anh em của nhánh chứa đỉnh ~B~, còn ~B~ sẽ đi trong cây con của ~u_{i+1}~
Gọi ~dp_u~ là kết quả tối ưu của ~B~ khi đi trong cây con gốc ~u~.
Gọi ~deep_u~ là khoảng cách xa nhất từ ~u~ đến một nút lá trong cây con gốc ~u~
Gọi ~h_u~ là độ sâu của nút ~u~ trên cây
Gọi ~ma_u~ là ~deep_v~ lớn nhất trong các ~v~ là con của ~u~ nhưng không phải là ~u_i~ nào đó
Ta có công thức tính ~dp_{u_i}~ như sau:
- ~dp_{u_i} = deep_{u_i} + 1~ ( Nếu ~u_i = B~ )
- ~dp_{u_i} = max(dp_{u_{i+1}}, h_B − h_u + ma_u + 1)~ ( Nếu ~ui \neq B~ )
Và với mỗi đỉnh ~u_1~, ~u_2~, ~\dots~, ~u_{k−1}~ ta cập nhập ~ans~ thành: ~max(ans,min(dp_u, h_u + ma_u + 1))~
Code mẫu
#include <iostream> #include <stdio.h> #include <vector> #include <cmath> #include <math.h> #include <map> #include <algorithm> #include <set> #include <bitset> #include <queue> #include <cstring> #include <stack> #include <iomanip> #include <assert.h> #define BIT(x,pos) (((x)>>(pos)) & 1LL) #define _(x) (1LL<<(x)) #define bitCnt(x) __builtin_popcountll(x) #define turnOn(x,pos) ((x) = (_(pos))) #define turnOff(x,pos) ((x) &= ~(_(pos))) #define flipBit(x,pos) ((x) ^= (_(pos))) #define lowBit(x) ((x) & (-x)) #define turnAll(x) (_(x)-1LL) #define name "test" #define nameTask "" #define fastIO ios::sync_with_stdio(false); cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; const int N = 2E5; const int INF = 2E9; bool visited[N+9]; vector<int> adj[N+9]; int nodeA, nodeB; vector<int> pathNode; int f[N+9]; int high[N+9]; int n; bool maximize(int &x, int y) { if (x < y) { x = y; return true; } return false; } void pathCreate(int u, int p) { for (int i = 0;i < (int)adj[u].size(); ++i) { int v = adj[u][i]; if (v == p) continue; pathCreate(v, u); visited[u] |= visited[v]; } if (visited[u] == 1) pathNode.push_back(u); } void dfsUp(int u,int p) { f[u] = 1; for (int i = 0;i < (int)adj[u].size(); ++i) { int v = adj[u][i]; if (v == p) continue; high[v] = high[u] + 1; dfsUp(v, u); if (visited[v] == 1) continue; maximize(f[u], f[v] + 1); } } int main() { if (fopen(name".INP","r")) freopen(name".INP","r",stdin), freopen(name".OUT","w",stdout); fastIO cin>>n; for (int i = 1;i < n;++i) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } cin>>nodeA>>nodeB; visited[nodeB] = 1; high[nodeA] = 1; pathCreate(nodeA,nodeA); dfsUp(nodeA, nodeA); reverse(pathNode.begin(),pathNode.end()); int res = -INF; int distA = 0, distB = 0; for (int i = 0;i+1 < (int)pathNode.size(); ++i) { int u = pathNode[i]; int v = pathNode[i+1]; distA = max(distA, high[u] - high[nodeA] + f[u]); distB = high[nodeB] - high[v] + f[v]; maximize(res, min(distA, distB)); } cout<<res; }
Bình luận