[Hackerearth] Leafonomics

Problem Link    : Leafonomics 
Category        : DP on Tree
Contest         : January Circuits '24 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int INF = 1e18;
 
struct Node {
    int v, w;
    Node(int v = 0, int w = 0)
        : v(v), w(w) {}
};
 
int n;
vector<vector<Node>> graph;
vector<int> in;
 
void dfs(int u, int p) {
    int &mini = in[u];
    mini = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        dfs(v, u);
        mini = min(mini, w + in[v]);
    }
    if (mini == INF) {
        mini = 0;
    }
}
 
vector<int> out;
 
void solve(int u, int p) {
    int firstMin = INF;
    int secondMin = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int cur = w + in[v];
        if (cur < firstMin) {
            secondMin = firstMin;
            firstMin = cur;
        } else if (cur < secondMin) {
            secondMin = cur;
        }
    }
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int use = w + in[v] == firstMin ? secondMin : firstMin;
        out[v] = min(w + out[u], w + use);
        solve(v, u);
    }
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    in.clear(); in.resize(n + 1);
    dfs(1, 0);
    out.clear(); out.resize(n + 1, INF);
    solve(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << min(in[i], out[i]) << " \n"[i == n];
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}

[Codeforces] F. Minimum Maximum Distance

Problem Link    : F. Minimum Maximum Distance
Category        : Approximate Problem
Contest         : Codeforces Round 903 (Div. 3) 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n, k;
        cin >> n >> k;
        vector<int> colors(n + 1);
        for (int i = 0; i < k; i++) {
            int u;
            cin >> u;
            colors[u] = 1;
        }
        vector<vector<int>> graph(n + 1);
        for (int e = 1; e < n; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        vector<int> in(n + 1, -1);
        function<void(int, int)> SolveIn = [&](int u, int p) {
            if (colors[u] == 1) {
                in[u] = 0;
            }
            for (int v : graph[u]) {
                if (v == p) {
                    continue;
                }
                SolveIn(v, u);
                if (~in[v]) {
                    in[u] = max(in[u], 1 + in[v]);
                }
            }
        };
        SolveIn(1, 0);
        vector<int> out(n + 1, -1);
        function<void(int, int)> SolveOut = [&](int u, int p) {
            if (colors[u]) {
                out[u] = max(out[u], 0ll);
            }
            int max1 = -1;
            int max2 = -1;
            for (int v : graph[u]) {
                if (v == p) {
                    continue;
                }
                if (in[v] > max1) {
                    max2 = max1;
                    max1 = in[v];
                } else if (in[v] > max2) {
                    max2 = max(max2, in[v]);
                }
            }
            for (int v : graph[u]) {
                if (v == p) {
                    continue;
                }
                int use = max1;
                if (in[v] == use) {
                    use = max2;
                }
                if (~use) {
                    out[v] = 2 + use;
                }
                if (~out[u]) {
                    out[v] = max(out[v], 1 + out[u]);
                }
                SolveOut(v, u);
            }
        };
        SolveOut(1, 0);
        int mini = INT_MAX;
        for (int i = 1; i <= n; i++) {
            mini = min({mini, max(in[i], out[i])});
        }
        if (mini == INT_MAX) {
            mini = 0;
        }
        cout << mini << endl;
    }
}
 

[Codeforces] D. Book of Evil

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Book of Evil
Source            : Codeforces
Category          : Graph Theory, Dynamic Programing
Algorithm         : DP on Tree, In Out DP
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, m, d;  
      cin >> n >> m >> d;  
      vector <int> evil(n + 1);  
      int root = -1;  
      for (int i = 1; i <= m; i++)  
      {  
            int x;  
            cin >> x;  
            evil[x] = 1;  
            if (root == -1) root = x;  
      }  
      vector < vector <int> > graph(n + 1);  
      for (int e = 1; e < n; e++)  
      {  
            int u, v;  
            cin >> u >> v;  
            graph[u].push_back(v);  
            graph[v].push_back(u);  
      }  
      vector <int> in(n + 1, 0);  
      vector <int> useful(n + 1);  
      function <void(int, int)> dfs = [&](int u, int p)  
      {  
            useful[u] = evil[u];  
            in[u] = evil[u] ? 1 : 0;  
            for (int v : graph[u])  
            {  
                  if (v == p) continue;  
                  dfs(v, u);  
                  if (useful[v] == 1)  
                  {  
                        in[u] = max(in[u], 1 + in[v]);  
                        useful[u] = 1;  
                  }  
            }  
      };  
      vector <int> out(n + 1);  
      out[root] = 1;  
      function <void(int, int)> solve = [&](int u, int p)  
      {  
            int max1 = 0;  
            int max2 = 0;  
            for (int v : graph[u])  
            {  
                  if (v == p) continue;  
                  if (in[v] >= max1) max2 = max1, max1 = in[v];  
                  else if (in[v] > max2) max2 = in[v];  
            }  
            for (int v : graph[u])  
            {  
                  if (v == p) continue;  
                  int use = max1;  
                  if (in[v] == use) use = max2;  
                  if (out[u]) out[v] = 1 + out[u];  
                  if (use) out[v] = max(out[v], 2 + use);  
                  solve(v, u);  
            }  
      };  
      dfs(root, 0);  
      solve(root, 0);  
      int ans = 0;  
      for (int i = 1; i <= n; i++)  
      {  
            int maxi = max(in[i], out[i]);  
            if (maxi > 0 and maxi - 1 <= d) ++ans;  
      }  
      cout << ans;  
}