Given two trees each of N nodes. Removing an edge of the tree partitions the tree in two subsets.
Find the total maximum number of distinct edges (e1, e2): e1 from the first tree and e2 from the second tree such that it partitions both the trees into subsets with same nodes.
Examples:
Input : Same as the above figure N = 6
Tree 1 : {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)}
Tree 2 :{(1, 2), (2, 3), (1, 6), (6, 5), (5, 4)}
Output : 1
We can remove edge 3-4 in the first graph and edge 1-6 in the second graph.
The subsets will be {1, 2, 3} and {4, 5, 6}.
Input : N = 4
Tree 1 : {(1, 2), (1, 3), (1, 4)}
Tree 2 : {(1, 2), (2, 4), (1, 3)}
Output : 2
We can select an edge 1-3 in the first graph and 1-3 in the second graph.
The subsets will be {3} and {1, 2, 4} for both graphs.
Also we can select an edge 1-4 in the first graph and 2-4 in the second graph.
The subsets will be {4} and {1, 2, 3} for both the graphs
Approach :
- The idea is to use hashing on trees, We will root both of trees at node 1, then We will assign random values to each node of the tree.
- We will do a dfs on the tree and, Suppose we are at node x, then we will keep a variable
subtree[x] that will store the hash value of all the nodes in its subtree. - One we did the above two steps, we are just left with storing the value of each subtree of nodes for both the trees the we get.
- We can use unordered map for it. The last step is to find how many common values of subtree[x] are there is both trees.
- Increase the count of distinct edges by +1 for every common values of subtree[x] for both trees.
Below is the implementation of above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const long long p = 97, MAX = 300005;// This function checks whether// a node is leaf node or not.bool leaf1(long long NODE, long long int deg1[]){ if (deg1[NODE] == 1 and NODE != 1) return true; return false;}// This function calculates the Hash sum// of all the children of a// particular node for subtree 1void dfs3(long long curr, long long par, vector<long long int> tree1[], long long int subtree1[], long long int deg1[], long long int node[]){ for (auto& child : tree1[curr]) { if (child == par) continue; dfs3(child, curr, tree1, subtree1, deg1, node); } // If the node is leaf node then // there is no child, so hash sum // will be same as the // hash value for the node. if (leaf1(curr, deg1) == true) { subtree1[curr] = node[curr]; return; } long long sum = 0; // Else calculate hash sum of all the // children of a particular node, this is done // by iterating on all the children of a node. for (auto& child : tree1[curr]) { sum = sum + subtree1[child]; } // store the hash value for // all the subtree of current node subtree1[curr] = node[curr] + sum; return;}// This function checks whether// a node is leaf node or not.bool leaf2(long long NODE, long long int deg2[]){ if (deg2[NODE] == 1 and NODE != 1) return true; return false;}// This function calculates the Hash// sum of all the children of// a particular node for subtree 2.void dfs4(long long curr, long long par, vector<long long int> tree2[], long long int subtree2[], long long int deg2[], long long int node[]){ for (auto& child : tree2[curr]) { if (child == par) continue; dfs4(child, curr, tree2, subtree2, deg2, node); } // If the node is leaf node then // there is no child, so hash sum will be // same as the hash value for the node. if (leaf2(curr, deg2) == true) { subtree2[curr] = node[curr]; return; } long long sum = 0; // Else calculate hash sum of all // the children of a particular node, this is // done by iterating on all the children of a node. for (auto& child : tree2[curr]) { sum = sum + subtree2[child]; } // store the hash value for // all the subtree of current node subtree2[curr] = node[curr] + sum;}// Calculates x^y in logN time.long long exp(long long x, long long y){ if (y == 0) return 1; else if (y & 1) return x * exp(x, y / 2) * exp(x, y / 2); else return exp(x, y / 2) * exp(x, y / 2);}// This function helps in building the treevoid Insertt(vector<long long int> tree1[], vector<long long int> tree2[], long long int deg1[], long long int deg2[]){ // Building Tree 1 tree1[1].push_back(2); tree1[2].push_back(1); tree1[2].push_back(3); tree1[3].push_back(2); tree1[3].push_back(4); tree1[4].push_back(3); tree1[4].push_back(5); tree1[5].push_back(4); tree1[5].push_back(6); tree1[6].push_back(5); // Since 6 is a leaf node for tree 1 deg1[6] = 1; // Building Tree 2 tree2[1].push_back(2); tree2[2].push_back(1); tree2[2].push_back(3); tree2[3].push_back(2); tree2[1].push_back(6); tree2[6].push_back(1); tree2[6].push_back(5); tree2[5].push_back(6); tree2[5].push_back(4); tree2[4].push_back(5); // since both 3 and 4 are leaf nodes of tree 2 . deg2[3] = 1; deg2[4] = 1;}// Function to make the hash valuesvoid TakeHash(long long n, long long int node[]){ // Take a very high prime long long p = 97 * 13 * 19; // Initialize random values to each node . for (long long i = 1; i <= n; ++i) { // A good random function is // chosen for each node . long long val = (rand() * rand() * rand()) + rand() * rand() + rand(); node[i] = val * p * rand() + p * 13 * 19 * rand() * rand() * 101 * p; p *= p; p *= p; }}// Function that returns the required answervoid solve(long long n, vector<long long int> tree1[], vector<long long int> tree2[], long long int subtree1[], long long int subtree2[], long long int deg1[], long long int deg2[], long long int node[]){ // Do dfs on both trees to // get subtree[x] for each node. dfs3(1, 0, tree1, subtree1, deg1, node); dfs4(1, 0, tree2, subtree2, deg2, node); // cnt_tree1 and cnt_tree2 is used // to store the count of all // the hashes of every node . unordered_map<long long, long long> cnt_tree1, cnt_tree2; vector<long long> values; for (long long i = 1; i <= n; ++i) { long long value1 = subtree1[i]; long long value2 = subtree2[i]; // Store the subtree value of tree 1 // in a vector to compare it later // with subtree value of tree 2. values.push_back(value1); // increment the count of hash // value for a subtree of a node. cnt_tree1[value1]++; cnt_tree2[value2]++; } // Stores the sum of all the hash values // of children for root node of subtree 1. long long root_tree1 = subtree1[1]; long long root_tree2 = subtree2[1]; // Stores the sum of all the hash values // of children for root node of subtree 1. cnt_tree1[root_tree1] = 0; cnt_tree2[root_tree2] = 0; long long answer = 0; for (auto& x : values) { // Check if for a given hash value for // tree 1 is there any hash value which // matches to hash value of tree 2 // If yes, then its possible to divide // the tree for this hash value // into two equal subsets. if (cnt_tree1[x] != 0 and cnt_tree2[x] != 0) ++answer; } cout << answer << endl;}// Driver Codeint main(){ vector<long long int> tree1[MAX], tree2[MAX]; long long int node[MAX], deg1[MAX], deg2[MAX]; long long int subtree1[MAX], subtree2[MAX]; long long n = 6; // To generate a good random function srand(time(NULL)); Insertt(tree1, tree2, deg1, deg2); TakeHash(n, node); solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node); return 0;} |
Output:
1
Time Complexity : O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!