Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<vector<int> > graph(30050);
- int a, b, n, t, curr_time = 0, answer = 0;
- struct vertex
- {
- int time_in, time_out, h;
- };
- vertex vertices[30050];
- void dfs(int v, int h)
- {
- vertices[v].time_in = curr_time;
- vertices[v].h = h;
- for (int i = 0; i < graph[v].size(); i++)
- {
- curr_time++;
- dfs(graph[v][i], h + 1);
- curr_time++;
- }
- vertices[v].time_out = curr_time;
- }
- int main(){
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- cin >> n >> a >> b;
- for (int i = 1; i < n; i++)
- {
- cin >> t;
- graph[t - 1].push_back(i);
- }
- dfs(0, 0);
- for (int i = 1; i < n; i++)
- if (vertices[i].time_in <= vertices[a - 1].time_in && vertices[a - 1].time_out <= vertices[i].time_out && vertices[i].time_in <= vertices[b - 1].time_in && vertices[b - 1].time_out <= vertices[i].time_out && vertices[answer].h < vertices[i].h)
- answer = i;
- cout << answer + 1;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement