1#include <stdbool.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6int timeRequired = 0;
7
8void dfs(int node, int parent, int** adjList, int* adjSize, bool* hasApple) {
9    for (int i = 0; i < adjSize[node]; ++i) {
10        int child = adjList[node][i];
11        if (child == parent) continue;
12        dfs(child, node, adjList, adjSize, hasApple);
13        if (hasApple[child]) {
14            timeRequired += 2;
15            hasApple[node] = true;
16        }
17    }
18}
19
20int minTime(int n, int** edges, int edgesSize, bool* hasApple) {
21    int* adjSize = (int*)calloc(n, sizeof(int));
22    int** adjList = (int**)malloc(n * sizeof(int*));
23
24    for (int i = 0; i < n; ++i) {
25        adjList[i] = (int*)malloc((n - 1) * sizeof(int));
26    }
27
28    for (int i = 0; i < edgesSize; ++i) {
29        int u = edges[i][0];
30        int v = edges[i][1];
31        adjList[u][adjSize[u]++] = v;
32        adjList[v][adjSize[v]++] = u;
33    }
34
35    dfs(0, -1, adjList, adjSize, hasApple);
36
37    for (int i = 0; i < n; ++i) {
38        free(adjList[i]);
39    }
40    free(adjList);
41    free(adjSize);
42
43    return timeRequired;
44}