road repair hackerrank problem solving solution github

1#include <algorithm>
2#include <cstdio>
3#include <deque>
4#include <utility>
5#include <vector>
6using namespace std;
7
8typedef pair<int, int> pii;
9#define REP(i, n) for (int i = 0; i < (n); i++)
10#define fi first
11#define mp make_pair
12#define pb push_back
13#define se second
14
15int ri()
16{
17  int x;
18  scanf("%d", &x);
19  return x;
20}
21
22const int N = 100000;
23vector<int> e[N];
24
25// {C, {A, B}}
26// C: whether A covers the parent edge
27// A: cost of subtree(v)
28// B: cost of subtree(v)+parent edge; parent edge is the end of some path
29// A <= B <= A+1
30pair<bool, pii> dfs(int v, int p)
31{
32  deque<pii> c;
33  int t = -1;
34  bool has = false;
35  for (auto u: e[v])
36    if (u != p) {
37      auto r = dfs(u, v);
38      if (! r.fi)
39        has = true;
40      if (r.se.fi == r.se.se)
41        c.push_front(r.se);
42      else
43        c.pb(r.se);
44      t = u;
45    }
46  if (c.empty())
47    return {false, pii{0, 1}};
48  bool cover = false;
49  int f = 0, g = 0, i = 0;
50  for (; i+1 < c.size() && c[i+1].fi == c[i+1].se; i += 2) // beneficial to pair B if the A=B for some child
51    f += c[i].se+c[i+1].se-1, cover = true;
52  if (i < c.size()) {
53    g = f+c[i].se;
54    if (c[i].fi == c[i].se)
55      cover = true;
56    // if A < B for all children and some child is uncovered
57    f += ! cover && has ? cover = true, c[i].se : c[i].fi;
58    while (++i < c.size())
59      f += c[i].fi, g += c[i].fi;
60  } else
61    g = f+1; // all children are paired, one more edge is needed to cover the parent edge
62  return {cover, {f, g}};
63}
64
65int main()
66{
67  for (int cc = ri(); cc--; ) {
68    int n = ri();
69    REP(i, n)
70      e[i].clear();
71    REP(i, n-1) {
72      int u = ri(), v = ri();
73      e[u].pb(v);
74      e[v].pb(u);
75    }
76    printf("%d\n", dfs(0, -1).se.fi);
77  }
78}
79