# ABC 428 E - Farthest Vertex ```cpp= #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXN = 500005; vector<int> grid[MAXN]; vector<int> bfs(int start, int n) { vector<int> dist(n + 1, -1); queue<int> q; dist[start] = 0; q.push(start); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : grid[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } return dist; } int find_furthest(const vector<int>& dist) { int maxDist = -1, node = -1; for (int i = 1; i < dist.size(); ++i) { if (dist[i] > maxDist || (dist[i] == maxDist && i > node)) { maxDist = dist[i]; node = i; } } return node; } int main() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; grid[u].push_back(v); grid[v].push_back(u); } vector<int> dist1 = bfs(1, n); int x = find_furthest(dist1); vector<int> distX = bfs(x, n); int y = find_furthest(distX); vector<int> distY = bfs(y, n); for (int v = 1; v <= n; ++v) { if (distX[v] > distY[v]) { cout << x << endl; } else if (distY[v] > distX[v]) { cout << y << endl; } else { cout << max(x, y) << endl; } } return 0; }
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up