Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<vector<int> > graph(200000);
- vector <int> dist(200000, 0), used(200000, 0);
- void dfs(int v, int h) {
- dist[v] = h;
- used[v] = 1;
- for (int i = 0; i < graph[v].size(); i++) {
- if (!used[graph[v][i]]) dfs(graph[v][i], h + 1);
- }
- }
- int max_el(vector <int> num) {
- int res = -10000000000;
- for (int i = 0; i < num.size(); i++) {
- if (num[i] > res) res = num[i];
- }
- return res;
- }
- int main(){
- int n, m, v, u;
- cin >> n >> m;
- graph.resize(n);
- dist.resize(n);
- used.resize(n);
- vector <int> tree(n);
- for (int i = 0; i < n - 1; i++) {
- cin >> tree[i];
- graph[tree[i] - 1].push_back(i + 1);
- graph[i + 1].push_back(tree[i] - 1);
- }
- dfs(0, 0);
- int depth = max_el(dist);
- int max_d = -100000000000000;
- for (int i = 0; i < dist.size(); i++) {
- if (dist[i] > max_d) {
- max_d = dist[i];
- v = i;
- }
- }
- for (int i = 0; i < n; i++) {
- used[i] = 0;
- }
- dfs(v, 0);
- max_d = -10000000000000;
- for (int i = 0; i < n; i++) {
- if (dist[i] > max_d) {
- max_d = dist[i];
- u = i;
- }
- }
- if (m == 1) {
- cout << max_d + 1;
- }
- else if (max_d == 1) {
- cout << 1 + m * 2;
- }
- else {
- cout << max_d + (m - 1) * 2 + depth * (m - 1) * 2 + 1;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement