# CONQUEROR - Editorial

**URL:** <https://discuss.codechef.com/t/conqueror-editorial/116392>\
**Category:** editorial\
**Tags:** dynamic-programming, editorial, trees, start123\
**Created:** [February 28, 2024, 5:00pm UTC](https://discuss.codechef.com/t/conqueror-editorial/116392 "2024-02-28T17:00:16Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [February 28, 2024, 5:00pm UTC](https://discuss.codechef.com/t/conqueror-editorial/116392/1 "2024-02-28T17:00:16Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/CONQUEROR)  
[Contest: Division 1](https://www.codechef.com/START123A/problems/CONQUEROR)  
[Contest: Division 2](https://www.codechef.com/START123B/problems/CONQUEROR)  
[Contest: Division 3](https://www.codechef.com/START123C/problems/CONQUEROR)  
[Contest: Division 4](https://www.codechef.com/START123D/problems/CONQUEROR)

_ **Author:** _ [evenvalue](https://www.codechef.com/users/evenvalue)  
_ **Tester:** _ [apoorv\_me](https://www.codechef.com/users/apoorv_me)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093)

# DIFFICULTY:

TBD

# PREREQUISITES:

DFS, dynamic programming

# PROBLEM:

You have a tree with N vertices rooted at vertex 1, and an integer K.  
Starting at vertex 1, you can do the following operations:

- If you’re standing on a leaf, consider it conquered.  
Then, choose some k (1 \leq k \leq K), and move to the k-th ancestor of this leaf.
- If you’re not on a leaf, move to one of its children.

What’s the maximum number of distinct leaves that can be conquered?

# EXPLANATION:

The only way to move up the tree is to reach a leaf and then pick one of its ancestors.

This means an optimal sequence of moves will look as follows:

- Start at vertex 1, and choose one of its children (say v\_1).  
Move to v\_1.
- Perform some moves within the subtree of v\_1, conquering as many leaves as possible.  
Then, use a leaf to jump back to vertex 1, and never enter v\_1 again.
- Next, pick another child v\_2, and do the same thing.  
\vdots
- Finally, pick a child v\_k of 1, from which you _won’t return to 1_ (either by choice, or because it’s impossible to do so).  
Move to v\_k, and solve for it.

This leads us to a dynamic programming solution.  
Define:

- \text{ans}[u] to be the maximum number of leaves that can be conquered in the subtree of u.
- \text{return}[u] to be the maximum number of leaves that can be conquered in the subtree of u, if you start at u and are still able to return to it afterwards.

The answer we want is \text{ans}[1].

Let’s attempt to compute these two arrays, starting with \text{return}.  
Suppose you’re at a vertex u, and v is one of its children.  
If it’s possible to visit v, perform some moves in the subtree of v, and then return to u, we make the following observations:

- First, there should be a leaf that’s “high enough” that it can be used to return to u at all.  
That is, there should exist a leaf x in the subtree of x such that the depth of x is _at most_ \text{dep}[u] + K.  
This is easy to check: it’s enough to compute the highest leaf in the subtree of v, and then check if it satisfies this condition.
- Second, notice that it’s also possible to use the same sequence of moves to end up at v instead of u (on the final upward move, you can choose to end up at v rather than u).  
Conversely (provided the “high enough” leaf exists), any sequence of moves that starts at v and ends up at v can be extended to end at u instead, by first ending at v, then moving down to this leaf and then moving up to u.  
This means the best value that can be obtained from this subtree is exactly \text{return}[v].

This makes \text{return}[u] quite simple to compute.  
For each child v of u, if there exists a high enough leaf in the subtree of v, add \text{return}[v] to \text{return}[u].  
If u is a leaf, \text{return}[u] = 1.  
Computing the highest leaves in every subtree is easily done with a DFS.

* * *

Now that we know all the \text{return}[u] values, let’s compute the \text{ans}[u] values.

As noted at the start, when computing \text{ans}[u], we can choose _at most one_ child v, and go into it without ever returning to u.  
That is, for every child v of u except maybe one, the value we take will still be just \text{return}[v] (or 0, if a high enough leaf doesn’t exist).

In other words, we start with \text{ans}[u] = \text{return}[u], and then for exactly one child, we’ll _replace_ \text{return}[v] with \text{ans}[v].  
Since we want to maximize the sum, clearly it’s best to choose whichever child has the highest value of \text{ans}[v] - \text{return}[v].

So, quite simply, all that needs to be done is to find the highest value of \text{ans}[v] - \text{return}[v] across all children; and set \text{ans}[u] to be \text{return}[u] plus this maximum.

This is easily done with a DFS, and can even just be done when computing the \text{return}[u] values.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

[details = Author’s code (C++)]

```cpp
#include <bits/stdc++.h>
using namespace std;

namespace Read {
int Int() {
  int x;
  cin >> x;
  return x;
}
}//namespace Read

constexpr int kInf = 1e9 + 10;

inline void solution() {
  const int n = Read::Int();
  const int k = Read::Int();

  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    const int x = Read::Int() - 1;
    const int y = Read::Int() - 1;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  vector<int> depth(n);
  vector<int> shallow(n, kInf);
  
  auto is_sink = [&](const int x) {
    return shallow[x] - depth[x] >= k;
  };

  vector<int> recoil(n);
  vector<int> best(n);

  function<void(int, int)> dfs = [&](const int x, const int p) {
    if (p != -1 and g[x].size() == 1) {
      shallow[x] = depth[x];
      recoil[x] = 1;
      best[x] = 1;
    }
    for (const int y : g[x]) {
      if (y == p) continue;
      depth[y] = depth[x] + 1;
      dfs(y, x);
      shallow[x] = min(shallow[x], shallow[y]);
      if (not is_sink(y)) {
        recoil[x] += recoil[y];
      }
    }
    int extra = 0;
    for (const int y : g[x]) {
      if (y == p) continue;
      extra = max(extra, best[y] - (is_sink(y) ? 0 : recoil[y]));
    }
    best[x] = recoil[x] + extra;
  };

  dfs(0, -1);
  cout << best[0] << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int testcases = 1;
  cin >> testcases;
  while (testcases--) {
    solution();
  }
}

```

[/details]  
[details = Tester’s code (C++)]

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	
	int T; cin >> T;
	while(T-- > 0) {
	    int N, K; cin >> N >> K;
	    vector<vector<int>> adj(N);
	    for(int i = 1 ; i < N ; ++i) {
	        int u, v; cin >> u >> v;
	        adj[u - 1].push_back(v - 1);
	        adj[v - 1].push_back(u - 1);
	    }
	    int ans = 1;
	    function<array<int, 3>(int, int)> dfs = [&](int node, int par) -> array<int, 3> {
	        vector<array<int, 3>> sol;
	        for(auto &u: adj[node]) if(u != par) {
	            sol.push_back(dfs(u, node));
	        };
	        if(sol.empty()) {
	            return {1, 1, 1};
	        }
	        sort(sol.rbegin(), sol.rend());
	        int count = 0, hh = sol.front()[0];
	        int mx = 0;
	        for(auto &[h, v, b]: sol) {
	            if(h <= K) {
	                count += v;
	                mx = max(mx, b - v);
	            } else {
	                mx = max(mx, b);
	            }
	            hh = h;
	        }
	        ans = max(ans, count + mx);
	        return {hh + 1, count, count + mx};
	    };
	    dfs(0, -1);
	    cout << ans << '\n';
	}
}

```

[/details]  
[details = Editorialist’s code (C++)]

```cpp
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector adj(n, vector<int>());
        for (int i = 0; i < n-1; ++i) {
            int u, v; cin >> u >> v;
            adj[--u].push_back(--v);
            adj[v].push_back(u);
        }
        vector<int> dp1(n), dp2(n);
        auto dfs = [&] (const auto &self, int u, int p, int dep = 0) -> int {
            int mnleaf = n+1;
            bool isleaf = true;
            int bestinc = 0;
            for (int v : adj[u]) {
                if (v == p) continue;
                int high = self(self, v, u, dep + 1);
                isleaf = false;
                mnleaf = min(mnleaf, high);

                if (dep + k >= high) {
                    dp2[u] += dp2[v];
                    bestinc = max(bestinc, dp1[v] - dp2[v]);
                }
                else {
                    bestinc = max(bestinc, dp1[v]);
                }
            }
            if (isleaf) {
                dp1[u] = dp2[u] = 1;
                return dep;
            }
            dp1[u] = dp2[u] + bestinc;
            return mnleaf;
        };
        dfs(dfs, 0, 0);
        cout << dp1[0] << '\n';
    }
}

```

[/details]

---

<div class="post-metadata">

**Author:** ![naman\_agarwal](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naman_agarwal/32/208155_2.png) [@naman\_agarwal](https://discuss.codechef.com/u/naman_agarwal)\
**Post date:** [February 28, 2024, 5:07pm UTC](https://discuss.codechef.com/t/conqueror-editorial/116392/2 "2024-02-28T17:07:45Z")

</div>

[https://www.codechef.com/viewsolution/1047839096](https://www.codechef.com/viewsolution/1047839096)

Can someone tell me why is this giving wrong answer?

---

<div class="post-metadata">

**Author:** ![venkateshk1220](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@venkateshk1220](https://discuss.codechef.com/u/venkateshk1220)\
**Post date:** [February 28, 2024, 5:49pm UTC](https://discuss.codechef.com/t/conqueror-editorial/116392/3 "2024-02-28T17:49:13Z")

</div>

I have also failed in the same ☹  
Input:  
1  
8 2  
2 3  
3 8  
5 8  
6 7  
7 4  
4 1  
1 8

Tree Representation:

```auto
                 1
               / \ 
              8 4
             / \ \
            5 3 7
                 \ \
                  2 6

```

Expected Answer: 3  
You may give : 2  
Path:  
1 → 8 → 3 → 2 (Jump)-\> 8 → 5 (Jump) → 1 → 4 → 7 → 6

**visited 5, 2, and 6**

---

<div class="post-metadata">

**Author:** ![naman\_agarwal](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naman_agarwal/32/208155_2.png) [@naman\_agarwal](https://discuss.codechef.com/u/naman_agarwal)\
**Post date:** [February 28, 2024, 6:37pm UTC](https://discuss.codechef.com/t/conqueror-editorial/116392/4 "2024-02-28T18:37:32Z")

</div>

Thanks for this edge case… Will rectify my code for this

---

<div class="post-metadata">

**Author:** ![snapper\_002](https://discuss.codechef.com/user_avatar/discuss.codechef.com/snapper_002/32/24644_2.png) [@snapper\_002](https://discuss.codechef.com/u/snapper_002)\
**Post date:** [February 29, 2024, 6:09am UTC](https://discuss.codechef.com/t/conqueror-editorial/116392/5 "2024-02-29T06:09:20Z")

</div>

Hate the Statement  
I think that i can go to leaf exactly once, since first step says we have to mark to conquered and Other way it says we can conquer just once

Otherwise Problem is quite easy (if statement is correct)