#### B. Binary-tree-array: ↵
↵
<spoiler summary="Tutorial">↵
B. Binary-tree-array:↵
---------------------↵
↵
Just convert the string into binary notation.<br>↵
ie:L to 0 and R to 1.<br>↵
let that value be b in decimal.<br>↵
then the answer will be `2^n+b`.↵
<br>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.↵
<br>note: hidden node will be at height n.↵
<br>Overall complexity: O(29*q) worst case.<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
Left child of a node at ith position in array will be at 2*i th position.↵
<br> similarly right child will be at 2*i+1 position in same array.↵
<br>So, using the given left or right information, we can recursively find position of hidden node, starting from i=1.↵
<br>Overall complexity: O(29*q) worst case.↵
<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### C. Edge-vs-node-mapping: ↵
↵
<spoiler summary="Tutorial">↵
C. Edge-vs-node-mapping:↵
------------------------↵
↵
Tree has one property that all the nodes except root node will have exactly one parent node.↵
<br>So for all node except root node, we can map the node with edge connecting it with it's parent node.↵
<br>This can be done with dfs with assuming some random node root.↵
<br>Overall complexity: O(n).<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
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.↵
<br>Overall complexity: O(n).<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### D. MAX-MIN: ↵
↵
<spoiler summary="Tutorial">↵
B. MAX-MIN:↵
---------------------↵
↵
It is just an implementation problem.↵
<br>↵
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.<br>↵
<br> 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.↵
<br>ie:it will have only one edge(ie:adj[par].size()==1).<br>↵
<br> Do this upto k iterations and then do dfs on final tree to find the ans.↵
<br>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)).↵
<br>Overall complexity: O(n*log(n)) worst case.↵
<br>where dfs takes O(n) but adjacency set insertion and leaf removal will take O(n*log(n)) worst case. ↵
<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
<br>↵
it can also be done without doing any of k iterations but just one dfs from initial tree, and no removal of edges.↵
<br>the maximum in final tree will be just `maximum length in initial tree - maximum length in final tree`.↵
<br>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.↵
<br>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.↵
<br>Below is implementation of above approach.↵
<br><br>Overall complexity: O(n) worst case.<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="Tutorial">↵
B. Binary-tree-array:↵
---------------------↵
↵
Just convert the string into binary notation.<br>↵
ie:L to 0 and R to 1.<br>↵
let that value be b in decimal.<br>↵
then the answer will be `2^n+b`.↵
<br>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.↵
<br>note: hidden node will be at height n.↵
<br>Overall complexity: O(29*q) worst case.<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
Left child of a node at ith position in array will be at 2*i th position.↵
<br> similarly right child will be at 2*i+1 position in same array.↵
<br>So, using the given left or right information, we can recursively find position of hidden node, starting from i=1.↵
<br>Overall complexity: O(29*q) worst case.↵
<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### C. Edge-vs-node-mapping: ↵
↵
<spoiler summary="Tutorial">↵
C. Edge-vs-node-mapping:↵
------------------------↵
↵
Tree has one property that all the nodes except root node will have exactly one parent node.↵
<br>So for all node except root node, we can map the node with edge connecting it with it's parent node.↵
<br>This can be done with dfs with assuming some random node root.↵
<br>Overall complexity: O(n).<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
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.↵
<br>Overall complexity: O(n).<br>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### D. MAX-MIN: ↵
↵
<spoiler summary="Tutorial">↵
B. MAX-MIN:↵
---------------------↵
↵
It is just an implementation problem.↵
<br>↵
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.<br>↵
<br> 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.↵
<br>ie:it will have only one edge(ie:adj[par].size()==1).<br>↵
<br> Do this upto k iterations and then do dfs on final tree to find the ans.↵
<br>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)).↵
<br>Overall complexity: O(n*log(n)) worst case.↵
<br>where dfs takes O(n) but adjacency set insertion and leaf removal will take O(n*log(n)) worst case. ↵
<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="alternative">↵
<br>↵
it can also be done without doing any of k iterations but just one dfs from initial tree, and no removal of edges.↵
<br>the maximum in final tree will be just `maximum length in initial tree - maximum length in final tree`.↵
<br>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.↵
<br>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.↵
<br>Below is implementation of above approach.↵
<br><br>Overall complexity: O(n) worst case.<br>↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
