211912026-01-12 16:58:24algoproLegtávolabbi leszármazottcpp17Accepted 50/5046ms6712 KiB
// UUID: 78510bb9-bfe4-4b3e-81c2-9fb1304e2d9e
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> children(N + 1);
    vector<int> hasParent(N + 1, 0);

    for (int i = 0; i < N - 1; i++) {
        int parent, child;
        cin >> parent >> child;
        children[parent].push_back(child);
        hasParent[child] = 1;
    }
    int root = 1;
    for (int i = 1; i <= N; i++) {
        if (!hasParent[i]) {
            root = i;
            break;
        }
    }
    queue<pair<int, int>> q;
    q.push({root, 0});
    int farthestNode = root;
    int maxDepth = 0;
    while (!q.empty()) {
        auto [u, depth] = q.front();
        q.pop();
        if (depth > maxDepth) {
            maxDepth = depth;
            farthestNode = u;
        }
        for (int v : children[u]) {
            q.push({v, depth + 1});
        }
    }
    cout << farthestNode << "\n";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/034ms4404 KiB
3Accepted1/11ms316 KiB
4Accepted3/31ms316 KiB
5Accepted3/31ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted1/11ms316 KiB
9Accepted2/237ms5092 KiB
10Accepted3/339ms4904 KiB
11Accepted3/31ms316 KiB
12Accepted4/441ms4996 KiB
13Accepted4/439ms5168 KiB
14Accepted3/34ms820 KiB
15Accepted3/341ms5168 KiB
16Accepted3/335ms4808 KiB
17Accepted3/339ms4776 KiB
18Accepted4/430ms4660 KiB
19Accepted4/432ms4404 KiB
20Accepted4/446ms6712 KiB