 MAXIMUM WEIGHT NODE 31.

}
1. #include <iostream> 32.
2. #include <vector> 33. Solu on s;
3. using namespace std; 34. cout << s.maxWeightCell(n, arr) << endl;
4. class Solu on { 35.
5. public: 36. return 0;
6. int maxWeightCell(int N, vector<int>& Edge) { 37. }
7. vector<long long> weight(N, 0); -------------------------------------------------------------------------------
8. for (int i = 0; i < N; ++i) {  largestSumCycle
9. if (Edge[i] != -1) { 1. #include <bits/stdc++.h>
10. weight[Edge[i]] += i; 2. using namespace std;
11. } 3. class Solu on {
12. } 4. public:
13. int maxIndex = -1; 5. vector<vector<int>> adj;
14. long long maxWeight = -1; 6. vector<int> visit, back, temp;
15. for (int i = 0; i < N; ++i) { 7. long long dfs(int node, int parent = -1) {
16. if (weight[i] > maxWeight || (weight[i] == maxWeight 8. visit[node] = 1;
&& i > maxIndex)) { 9. back[node] = parent;
17. maxWeight = weight[i]; 10. temp.push_back(node);
18. maxIndex = i; 11.
19. } 12. for (int neighbor : adj[node]) {
20. } 13. if (visit[neighbor] == 0) {
21. return maxIndex; 14. long long res = dfs(neighbor, node);
22. } 15. if (res != -1) return res;
23. }; 16. } else if (visit[neighbor] == 1) {
24. 17. long long sum = neighbor;
25. int main() { 18. while (node != neighbor) {
26. int n; 19. sum += node;
27. cin >> n; 20. node = back[node];
28. vector<int> arr(n); 21. }
29. for (int i = 0; i < n; ++i) { 22. return sum;
30. cin >> arr[i]; 23. }
24. } 56. cin >> N;
25. return -1; 57. vector<int> Edge(N);
26. } 58. for (int i = 0; i < N; ++i) {
27. long long largestSumCycle(int N, vector<int>& Edge) { 59. cin >> Edge[i];
28. long long maxSum = -1; 60. }
29. visit.assign(N, 0); 61. Solu on sol;
30. back.assign(N, -1); 62. long long result = sol.largestSumCycle(N, Edge);
31. adj.resize(N); 63. cout << result << endl;
32. 64. return 0;
33. for (int i = 0; i < N; ++i) { 65. }
34. if (Edge[i] != -1) {
------------------------------------------------------------------------------------------
35. adj[i].push_back(Edge[i]);
36. } NearestMee ngCell
37. }
38. for (int i = 0; i < N; ++i) { 1. #include <iostream>
39. if (!visit[i]) { 2. #include <vector>
40. long long cycleSum = dfs(i); 3. #include <queue>
41. if (cycleSum > maxSum) { 4. #include <climits>
42. maxSum = cycleSum; 5. using namespace std;
43. } 6. vector<int> bfs(int start, const vector<int>& edges, int N) {
44. for (int node : temp) { 7. vector<int> dist(N, INT_MAX);
45. visit[node] = 2; 8. queue<int> q;
46. } 9. dist[start] = 0;
47. temp.clear(); 10. q.push(start);
48. } 11. while (!q.empty()) {
49. } 12. int node = q.front();
50. return maxSum; 13. q.pop();
51. } 14. int next_node = edges[node];
52. }; 15. if (next_node != -1 && dist[next_node] == INT_MAX) {
53. 16. dist[next_node] = dist[node] + 1;
54. int main() { 17. q.push(next_node);
55. int N; 18. }
19. } 49. int C1, C2;
20. return dist; 50. cin >> C1 >> C2;
21. } 51. int result = nearestMee ngCell(N, edges, C1, C2);
22. int nearestMee ngCell(int N, const vector<int>& edges, int 52. cout << result << endl;
C1, int C2) { 53. }
23. vector<int> distFromC1 = bfs(C1, edges, N); 54. return 0;
24. vector<int> distFromC2 = bfs(C2, edges, N); 55. }
25. int minDist = INT_MAX;
26. int mee ngCell = -1;
27. for (int i = 0; i < N; ++i) {
28. if (distFromC1[i] != INT_MAX && distFromC2[i] !=
INT_MAX) {
29. int maxDist = max(distFromC1[i], distFromC2[i]);
30. if (maxDist < minDist) {
31. minDist = maxDist;
32. mee ngCell = i;
33. }
34. }
35. }
36. return mee ngCell;
37. }
38.
39. int main() {
40. int T;
41. cin >> T;
42. while (T--) {
43. int N;
44. cin >> N;
45. vector<int> edges(N);
46. for (int i = 0; i < N; ++i) {
47. cin >> edges[i];
48. }