fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5; // Max nodes
  5. vector<int> adj[N]; // Adjacency list
  6. int nodeValue[N]; // Stores the value (0 or 1) of each node
  7. int dp[N], dp2[N]; // DP arrays
  8.  
  9. // DFS function to compute longest path of 1's
  10. void dfs(int node, int parent) {
  11.     if (nodeValue[node] == 0) {
  12.         dp[node] = dp2[node] = 0;
  13.         return;
  14.     }
  15.  
  16.     dp[node] = 1; // At least the node itself
  17.     vector<int> childPaths; // Store child dp values
  18.  
  19.     for (int child : adj[node]) {
  20.         if (child == parent) continue;
  21.         dfs(child, node);
  22.         childPaths.push_back(dp[child]);
  23.     }
  24.  
  25.     // Sort child paths in descending order
  26.     sort(childPaths.rbegin(), childPaths.rend());
  27.  
  28.     // Longest vertical path
  29.     if (!childPaths.empty()) dp[node] += childPaths[0];
  30.  
  31.     // Longest V-path
  32.     if (childPaths.size() > 1) dp2[node] = 1 + childPaths[0] + childPaths[1];
  33. }
  34.  
  35. int main() {
  36.     int n;
  37.     cout << "Enter number of nodes: ";
  38.     cin >> n;
  39.  
  40.     cout << "Enter node values (0 or 1) for each node from 1 to " << n << ":\n";
  41.     for (int i = 1; i <= n; i++) {
  42.         cin >> nodeValue[i];
  43.     }
  44.  
  45.     cout << "Enter " << n-1 << " edges (parent child format):\n";
  46.     for (int i = 1; i < n; i++) {
  47.         int u, v;
  48.         cin >> u >> v;
  49.         adj[u].push_back(v);
  50.         adj[v].push_back(u);
  51.     }
  52.  
  53.     int root = -1;
  54.     for (int i = 1; i <= n; i++) {
  55.         if (nodeValue[i] == 1) {
  56.             root = i;
  57.             break;
  58.         }
  59.     }
  60.  
  61.     if (root == -1) {
  62.         cout << "Final Answer: 0 (No '1' in the tree)\n";
  63.         return 0;
  64.     }
  65.  
  66.     dfs(root, -1);
  67.  
  68.     int ans = 0;
  69.     for (int i = 1; i <= n; i++) {
  70.         ans = max({ans, dp[i], dp2[i]});
  71.     }
  72.  
  73.     cout << "Final Answer: " << ans << endl;
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 5948KB
comments (?)
stdin
copy 
Enter number of nodes: 10
Enter node values (0 or 1) for each node from 1 to 10:
0 1 1 0 1 0 1 1 0 1
Enter 9 edges (parent-child format):
1 2
1 3
2 4
4 5
3 6
3 7
7 8
8 9
8 10
stdout
copy 
Enter number of nodes: Enter node values (0 or 1) for each node from 1 to 0:
Enter -1 edges (parent child format):
Final Answer: 0 (No '1' in the tree)
https://ideone.com/S5jEwS
language:
C++ (gcc 8.3)
created:
8 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!