fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 100005;
  8.  
  9. int N;
  10. vector<int> stars(MAXN);            // Stars of each city
  11. vector<vector<int>> adj(MAXN);       // Adjacency list for the tree
  12. vector<int> dp(MAXN, 1);             // DP array to store the LIS ending at each city
  13. vector<bool> visited(MAXN, false);   // Visited array for DFS
  14.  
  15. // Depth-First Search to compute the longest increasing path
  16. void dfs(int node, int parent) {
  17.     visited[node] = true;
  18.  
  19.     for (int neighbor : adj[node]) {
  20.         if (neighbor == parent) continue;  // Skip the parent to avoid revisiting
  21.         if (!visited[neighbor]) {
  22.             dfs(neighbor, node);  // Recursively explore neighbors
  23.  
  24.             // Update the dp array if we can eat at the neighbor
  25.             if (stars[neighbor] > stars[node]) {
  26.                 dp[neighbor] = max(dp[neighbor], dp[node] + 1);
  27.             } else if (stars[neighbor] < stars[node]) {
  28.                 dp[node] = max(dp[node], dp[neighbor] + 1);
  29.             }
  30.         }
  31.     }
  32. }
  33.  
  34. int main() {
  35.     cin >> N;
  36.  
  37.     // Input the stars of each city
  38.     for (int i = 1; i <= N; i++) {
  39.         cin >> stars[i];
  40.     }
  41.  
  42.     // Input the roads (edges)
  43.     for (int i = 1; i < N; i++) {
  44.         int u, v;
  45.         cin >> u >> v;
  46.         adj[u].push_back(v);
  47.         adj[v].push_back(u);
  48.     }
  49.  
  50.     // Start DFS from any node, here we start from city 1
  51.     dfs(1, -1);
  52.  
  53.     // The result is the maximum value in the dp array
  54.     int max_restaurants = *max_element(dp.begin() + 1, dp.begin() + N + 1);
  55.  
  56.     // Output the result
  57.     cout << max_restaurants << endl;
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 6204KB
comments (?)
stdin
copy 
7
4 1 3 2 5 3 6
1 2
1 3
1 4
4 5
4 6
5 7
stdout
copy 
2
https://ideone.com/fSXwx7
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!