dp-sol.cpp

/**
 * Update1: The solution didn't handle cases when a node covers its neighbours too
 * Update2: Tested with randomly generated test cases ~10K
 * Update3: Add an optimization to limit the max strength to range from -W to W, where W is the tree width
 * DISCLAIMER: 
 * This solution is written for explanation/educational purposes
 * and its intended to not follow coding guidelines or best practices
 * as the main intention is to explain the thinking strategy in a way
 * that's a little bit better than writing pseudo-code and to allow
 * student(s) to test and add debugging messages in every step.
 */
#include<iostream>
#include<map>
#include<set>
#include<unordered_set>
#include<vector>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

int N, W;
vector<int> G[1001];  // Tree structure
bool vis[1001][2];    // Visited array to mark visits as tree edges are bidirectional, to avoid inf loops
int mem[1500][1500];  // Holds minimum cost of covering subtree i, given that current strength = X+N (We use N here as strength could be negative)
int h[1500], f[1500]; // Holds tree height and max width for subtree i

/* Calculate height of tree */
int height(int i) {
    if (h[i] != -1) return h[i];
    vis[i][0] = true;

    int res = 0;
    for (int a = 0; a < G[i].size(); a++) {
        if (vis[G[i][a]][0]) continue;

        res = max(res, height(G[i][a])+1);
    }

    vis[i][0] = false;

    return (h[i] = res);
}

/* Calculate furthest 2 nodes, width of the tree */
int furthest(int i) {
    if (f[i] != -1) return f[i];
    vector<int> children;

    vis[i][1] = true;

    int res = height(i);
    for (int a = 0; a  < G[i].size(); a++) {
        if (vis[G[i][a]][1]) continue;
        children.push_back(height(G[i][a]));

        res = max(res, furthest(G[i][a]));
    }

    sort(children.rbegin(), children.rend());

    if (children.size() >= 2) {
        res = max(res, children[0]+children[1]+2);
    }

    vis[i][1] = false;

    return (f[i] = res);
}

/* Cost functio, You can use lambda here, didn't want to complicate the solution */
int cost(const int& strength) {
//      return strength;
    return strength + 1;
//    return (strength+1)*(strength+1);
//    return strength;
}

/* Calculate min cost of covering tree starting at i, given that current strength (can be negative) = s */
int solve(const int& i, const int& s) {
    if (mem[i][s+N] != -1) { // Calculated before
        return mem[i][s+N];
    } else if (G[i].size() == 0 || (G[i].size() == 1 && vis[G[i][0]][1])) { // A leaf
        int& val = mem[i][s+N];
        if (s > 0) return (val = 0);                // Already covered by one of its parents or neighbours
        else if (s == 0) return (val = cost(0));    // Not covered, build a 0 strength tower to cover itself
        else return (val = cost(abs(s)));           // Not covered, and some of its parents/neighbours at distance abs(s) are also not covered - build a tower of strength abs(s) to cover it and others
    }

    vis[i][1] = true;

    /* Loops in the below two branches are redundant and can be combined, but I've split them for readability purposes */
    int res = INT_MAX;
    if (s <= 0) {
        // Case #1: Build a tower in current node - loop all available strengths
        for (int st = abs(s); st <= W; st++) {
            int totChildStrength = cost(st);
            
            for (int a = 0; a < G[i].size(); a++) {
                if (vis[G[i][a]][1]) continue;

                totChildStrength += solve(G[i][a], st);
            }
            
            res = min(res, totChildStrength);
        }

    } else {
        // Case #2: The node is already covered, but why not check if we cover it with stronger towers, or use the current coverage to cover its children
        for (int st = s-1; st <= W; st++) {
            int totChildStrength = (st > (s-1) ? cost(st) : 0); // In case we use the coverage coming from parent/neighbours no cost incurred, otherwise calculate cost

            for (int a = 0; a < G[i].size(); a++)  {
                if (vis[G[i][a]][1]) continue;

                totChildStrength += solve(G[i][a], st);
            }

            res = min(res, totChildStrength);
        }
    }

    // Case #3: Covered by neighbours - This corner case is when a cell covers its parents and also its neighbours
    for (int st = -(W); st < s; st++) {
        int tot = 0;
        for (int a = 0; a < G[i].size(); a++) {
            if (vis[G[i][a]][1]) continue;
            tot += solve(G[i][a], abs(st)-1);
        }

        for (int a = 0; a < G[i].size(); a++) {
            if (vis[G[i][a]][1]) continue;
            res = min(res, tot-solve(G[i][a], abs(st)-1)+solve(G[i][a], st));
        }
    }

    vis[i][1] = false;

    return (mem[i][s+N] = res);
}

main() {

    cin >> N;
    int u, v;
    for (int i = 0; i < (N-1); i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    memset(mem, -1, sizeof mem);
    memset(vis, 0, sizeof vis);
    memset(f, -1, sizeof f);
    memset(h, -1, sizeof h);

    W = furthest(0); // Max strength = Width of the tree ;)

    cout << solve(0, 0) << endl; // Start ;)
}