Laskettelukeskus

#include <iostream>
#include <vector>

using namespace std;

struct Node {
  int id;
  long data;
  vector<Node*> children;
};

// Funtions
Node* create_node(long data, int id);

long eval(Node* root);

void insert(Node* root, int parent, Node* node);

int main()
{
  // n is the number of nodes in the tree
  int n;

  cin >> n;

  /* Syötteen lukeminen
  path start stores the parents of the nodes
  path end stores the ids of the nodes
  data stores the values (aurauskerrat) of the nodes
  */
  int path_start[n-1], path_end[n-1], data[n];

  for (int i = 0; i < n - 1; i++)
  {
    cin >> path_start[i] >> path_end[i];
  }

  for (int i = 0; i < n; i++)
  {
    cin >> data[i];
  }

  /* Algoritmi
  (1) make the root node
  (2) insert all of the other nodes
  (3) recursively find the number of (aurauskerrat) needed
  */
  Node* root = create_node(data[0], 1);

  for (int i = 1; i < n; i++)
  {
    Node* node = create_node(data[i], path_end[i-1]);
    insert(root, path_start[i-1], node);
  }

  cout << eval(root);
}

// A function for creating a new pointer to a node
Node* create_node(long data, int id)
{
  Node* node = new Node;
  node->data = data;
  node->id = id;
  return node;
}

// A function for inserting a node to the tree
/*
(1) Check if the root is the parent
(2) Go through the tree recursively to find the parent node
*/
void insert(Node* root, int parent, Node* node)
{
  if (root->id == parent)
  {
    root->children.push_back(node);
  }
  else
  {
    for (Node* child : root->children)
    {
      insert(child, parent, node);
    }
  }
}

// A function to determinen the number of snow plows needed
/*
(1) Go through the number the tree recursively (depth first search)
*/
long eval(Node* root)
{
  if (root->children.size() == 0) return root->data;
  long sum = 0;
  for (Node* child : root->children)
  {
    sum += eval(child);
  }
  return max(root->data, sum);
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED