Advertisement
Guest User

Untitled

a guest
Apr 24th, 2018
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector<vector<int> > graph(200000);
  7. vector <int> dist(200000, 0), used(200000, 0);
  8.  
  9. void dfs(int v, int h) {
  10. dist[v] = h;
  11. used[v] = 1;
  12. for (int i = 0; i < graph[v].size(); i++) {
  13. if (!used[graph[v][i]]) dfs(graph[v][i], h + 1);
  14. }
  15. }
  16.  
  17.  
  18. int max_el(vector <int> num) {
  19. int res = -10000000000;
  20. for (int i = 0; i < num.size(); i++) {
  21. if (num[i] > res) res = num[i];
  22. }
  23. return res;
  24. }
  25.  
  26.  
  27. int main(){
  28. int n, m, v, u;
  29. cin >> n >> m;
  30. graph.resize(n);
  31. dist.resize(n);
  32. used.resize(n);
  33. vector <int> tree(n);
  34. for (int i = 0; i < n - 1; i++) {
  35. cin >> tree[i];
  36. graph[tree[i] - 1].push_back(i + 1);
  37. graph[i + 1].push_back(tree[i] - 1);
  38. }
  39. dfs(0, 0);
  40. int depth = max_el(dist);
  41. int max_d = -100000000000000;
  42. for (int i = 0; i < dist.size(); i++) {
  43. if (dist[i] > max_d) {
  44. max_d = dist[i];
  45. v = i;
  46. }
  47. }
  48. for (int i = 0; i < n; i++) {
  49. used[i] = 0;
  50. }
  51. dfs(v, 0);
  52. max_d = -10000000000000;
  53. for (int i = 0; i < n; i++) {
  54. if (dist[i] > max_d) {
  55. max_d = dist[i];
  56. u = i;
  57. }
  58. }
  59. if (m == 1) {
  60. cout << max_d + 1;
  61. }
  62. else if (max_d == 1) {
  63. cout << 1 + m * 2;
  64. }
  65. else {
  66. cout << max_d + (m - 1) * 2 + depth * (m - 1) * 2 + 1;
  67. }
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement