Rating-Based Heatmap: Visualize Real Progress!

B. Binary-tree-array:

Just convert the string into binary notation.
ie:L to 0 and R to 1.
let that value be b in decimal.
then the answer will be 2^n+b.
where 2^n is the position of first node at height n, and b is distance between first node at height n and position of node having sequence of traversal(from root 1) as binary representation of b.
note: hidden node will be at height n.
Overall complexity: O(29*q) worst case.

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

int main()
{
    int h, q;
    cin >> h >> q;
    while (q--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        string m = "";
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'L')
                m += "0";
            else
                m += "1";
        }
        int ans = stoi(m,0,2);
        ans = (1 << n) | (ans);
        printf("%d\n", ans);
    }
    return 0;
}

Left child of a node at ith position in array will be at 2*i th position.
similarly right child will be at 2*i+1 position in same array.
So, using the given left or right information, we can recursively find position of hidden node, starting from i=1.
Overall complexity: O(29*q) worst case.

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

int main()
{
    int h, q;
    cin >> h >> q;
    while (q--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans=1;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'L')
                ans=2*ans;
            else
                ans=2*ans+1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Edge-vs-node-mapping:

Tree has one property that all the nodes except root node will have exactly one parent node.
So for all node except root node, we can map the node with edge connecting it with it's parent node.
This can be done with dfs with assuming some random node root.
Overall complexity: O(n).

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

void dfs(int root, int par, vector<int> arr[])
{
    for (auto &x : arr[root])
    {
        if (x == par)
            continue;

        printf("%d %d %d\n", x, root, x); // root is parent of x, so mapping them
        dfs(x, root, arr);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> arr[n + 1];
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    dfs(1, -1, arr); // choosing 1 as root
    return 0;
}

Same logic is used , but instead of doing dfs, we can do bottom up approach from leaf nodes to parent, as shown in below code.
Overall complexity: O(n).

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

int main()
{
    int n;
    scanf("%d",&n);
    vector<set<int>> arr(n + 1); 
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a].insert(b);
        arr[b].insert(a);
    }

    queue<int> leaf;

    for (int i = 1; i <= n; i++)
        if (arr[i].size() == 1)
            leaf.push(i);

    while (leaf.size() != 0)
    {
        int x = leaf.front();
        leaf.pop();

        if (x == 1)
            continue;

        int par = *arr[x].begin();
        printf("%d %d %d\n", x, par, x);
        arr[par].erase(x);
        if (arr[par].size() == 1)
            leaf.push(par);
    }

    return 0;
}

D. MAX-MIN:

It is just an implementation problem.
Have set of current leaf nodes in queue. And may use adjacency set representation instead of adjacency vector, so that edges can be added and removed in O(logn) worst case.

For each leaf node in current tree(from queue), just remove edges between it and it's parent, and add the parent to the queue if it became leaf for next iteration.
ie:it will have only one edge(ie:adj[par].size()==1).

Do this upto k iterations and then do dfs on final tree to find the ans.
ie:for each node, the maximum distance leaf node length will be 1+(max(maximum distance length of all immediate child nodes)), similarly minimum distance leaf length will be 1+(min(minimum distance length of all immediate child nodes)).
Overall complexity: O(n*log(n)) worst case.
where dfs takes O(n) but adjacency set insertion and leaf removal will take O(n*log(n)) worst case.

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

pair<int, int> dfs(vector<set<int>> &arr, int root, int par)
{

  int maxm = 0, minm = INT_MAX;
  for (auto &x : arr[root])
  {
    if (x == par)
      continue;

    pair<int, int> p = dfs(arr, x, root); // getting maxm and minm value of child node.
    maxm = max(maxm, p.first + 1);        // updating maxm to max of all child node maxm values.
    minm = min(minm, p.second + 1);       // updating minm to min of all child node minm values,
  }
  if (maxm == 0)
    minm = 0; // for leaf node.
  return {maxm, minm};
}

int main()
{
  int n, k;
  scanf("%d %d", &n, &k);
  vector<set<int>> arr(n + 1); // adjacency set representation for easy removal of edges.
  for (int i = 1; i <= n - 1; i++)
  {
    int a, b;
    scanf("%d %d", &a, &b);
    arr[a].insert(b);
    arr[b].insert(a);
  }

  queue<int> leaf;

  for (int i = 1; i <= n; i++)
    if (arr[i].size() == 1)
      leaf.push(i); //inserting first set of leaf nodes.

  int cnt = 0, m = 0, c = 0;
  while (leaf.size() != 0) // leaf nodes of current iteration tree and next iteration tree stored in same queue, but next iteration nodes present at the end.
  {
    if (c == m)
      c += leaf.size(), cnt += 1; // to differentiate between current tree and next tree
    m++;                          // cnt get incremented after each complete iteration.

    if (cnt > k) // cnt stores number of complete iteration happened so far.
      break;

    int x = leaf.front();
    leaf.pop();

    assert(x != 1 || leaf.size() == 0);
    if (x == 1) // reached root node, and after this, answer is always 0.
    {
      printf("0\n");
      return 0;
    }
    assert(arr[x].size() == 1);

    int par = *arr[x].begin(); // parent of current leaf node

    arr[par].erase(x); // removing edge between current leaf node from current tree.
    if (arr[par].size() == 1)
      leaf.push(par); // if parent node became new leaf node, then add it to the end of queue.
  }

  pair<int, int> p = dfs(arr, 1, -1); // to find ans in final tree.

  cout << p.first - p.second << "\n";

  return 0;
}

it can also be done without doing any of k iterations but just one dfs from initial tree, and no removal of edges.
the maximum in final tree will be just maximum length in initial tree - maximum length in final tree.
But finding minimum in final tree will need some modification, cause those nodes having it's minm length +1 < k should not pass it's value to parent, as it will removed before kth iteration.
so if all child nodes of a node has minm length + 1 < k then maximum of them should be chosen for current node otherwise minimum of minm length +1 from all child nodes such that minm length+1>k should be choosen for current node.
Below is implementation of above approach.

Overall complexity: O(n) worst case.

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

pair<int, int> dfs(vector<int> arr[], int root, int par, int k)
{

  int maxm = 0, minm;
  int mink2 = INT_MAX, mink1 = -1;
  for (auto &x : arr[root])
  {
    if (x == par)
      continue;

    pair<int, int> p = dfs(arr, x, root, k);
    maxm = max(maxm, p.first + 1); // same as previous method
    int minj = p.second + 1;       // but finding minm is different
    if (minj > k && minj < mink2)
    {
      mink2 = minj;
    }
    else if (minj < k && minj > mink1)
    {
      mink1 = minj;
    }
    else if (minj == k)
    {
      if (x == 1)
        mink2 = minj;
      else
        mink1 = minj;
    }
  }

  if (mink2 == INT_MAX)
    minm = mink1;
  else
    minm = mink2;

  if (maxm == 0)
    minm = 0; // for leaf node.
  return {maxm, minm};
}

int main()
{
  int n, k;
  scanf("%d %d", &n, &k);
  vector<int> arr[n + 1];
  for (int i = 1; i <= n - 1; i++)
  {
    int a, b;
    scanf("%d %d", &a, &b);
    arr[a].push_back(b);
    arr[b].push_back(a);
  }

  pair<int, int> p = dfs(arr, 1, -1, k);

  cout << p.first - p.second << "\n";

  return 0;
}