Number of distinct pair of edges such that it partitions both trees into same subsets of nodes
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:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
using namespace std;
const long long p = 97, MAX = 10;
bool leaf1(long long NODE, long long int deg1[]) {
return deg1[NODE] == 1 && NODE != 1;
}
void 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 (leaf1(curr, deg1)) {
subtree1[curr] = node[curr];
return;
}
long long sum = 0;
for (auto& child : tree1[curr]) {
sum += subtree1[child];
}
subtree1[curr] = node[curr] + sum;
}
bool leaf2(long long NODE, long long int deg2[]) {
return deg2[NODE] == 1 && NODE != 1;
}
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 (leaf2(curr, deg2)) {
subtree2[curr] = node[curr];
return;
}
long long sum = 0;
for (auto& child : tree2[curr]) {
sum += subtree2[child];
}
subtree2[curr] = node[curr] + sum;
}
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);
}
void Insertt(vector<long long int> tree1[], vector<long long int> tree2[], long long int deg1[], long long int deg2[]) {
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);
deg1[6] = 1;
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);
deg2[3] = 1;
deg2[4] = 1;
}
void TakeHash(long long n, long long int node[]) {
long long p = 97 * 13 * 19;
for (long long i = 1; i <= n; ++i) {
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;
}
}
void 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[]) {
dfs3(1, 0, tree1, subtree1, deg1, node);
dfs4(1, 0, tree2, subtree2, deg2, 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];
values.push_back(value1);
cnt_tree1[value1]++;
cnt_tree2[value2]++;
}
long long root_tree1 = subtree1[1];
long long root_tree2 = subtree2[1];
cnt_tree1[root_tree1] = 0;
cnt_tree2[root_tree2] = 0;
long long answer = 0;
for (auto& x : values) {
if (cnt_tree1[x] != 0 && cnt_tree2[x] != 0)
++answer;
}
cout << answer << endl;
}
int 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;
srand(time(NULL));
Insertt(tree1, tree2, deg1, deg2);
TakeHash(n, node);
solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node);
return 0;
}
import java.util.*;
public class TreeDivision {
// Prime number for hashing
static final long p = 97;
static final int MAX = 300005;
// Check whether a node is a leaf node or not for subtree 1
static boolean leaf1(int NODE, long[] deg1) {
return deg1[NODE] == 1 && NODE != 1;
}
// Calculate the hash sum of all the children of a node for subtree 1
static void dfs3(int curr, int par, List<Integer>[] tree1, long[] subtree1, long[] deg1, long[] node) {
for (int child : tree1[curr]) {
if (child == par)
continue;
dfs3(child, curr, tree1, subtree1, deg1, node);
}
// If the node is a leaf node, hash sum is the same as the node's hash value
if (leaf1(curr, deg1)) {
subtree1[curr] = node[curr];
return;
}
long sum = 0;
// Calculate hash sum of all children
for (int child : tree1[curr]) {
sum += subtree1[child];
}
// Store the hash value for all the subtree of the current node
subtree1[curr] = node[curr] + sum;
}
// Check whether a node is a leaf node or not for subtree 2
static boolean leaf2(int NODE, long[] deg2) {
return deg2[NODE] == 1 && NODE != 1;
}
// Calculate the hash sum of all the children of a node for subtree 2
static void dfs4(int curr, int par, List<Integer>[] tree2, long[] subtree2, long[] deg2, long[] node) {
for (int child : tree2[curr]) {
if (child == par)
continue;
dfs4(child, curr, tree2, subtree2, deg2, node);
}
// If the node is a leaf node, hash sum is the same as the node's hash value
if (leaf2(curr, deg2)) {
subtree2[curr] = node[curr];
return;
}
long sum = 0;
// Calculate hash sum of all children
for (int child : tree2[curr]) {
sum += subtree2[child];
}
// Store the hash value for all the subtree of the current node
subtree2[curr] = node[curr] + sum;
}
// Calculate x^y in logN time
static long exp(long x, long y) {
if (y == 0)
return 1;
else if (y % 2 == 1)
return x * exp(x, y / 2) * exp(x, y / 2);
else
return exp(x, y / 2) * exp(x, y / 2);
}
// Build the trees
static void Insertt(List<Integer>[] tree1, List<Integer>[] tree2, long[] deg1, long[] deg2) {
// Building Tree 1
tree1[1].add(2);
tree1[2].add(1);
tree1[2].add(3);
tree1[3].add(2);
tree1[3].add(4);
tree1[4].add(3);
tree1[4].add(5);
tree1[5].add(4);
tree1[5].add(6);
tree1[6].add(5);
// Since 6 is a leaf node for tree 1
deg1[6] = 1;
// Building Tree 2
tree2[1].add(2);
tree2[2].add(1);
tree2[2].add(3);
tree2[3].add(2);
tree2[1].add(6);
tree2[6].add(1);
tree2[6].add(5);
tree2[5].add(6);
tree2[5].add(4);
tree2[4].add(5);
// since both 3 and 4 are leaf nodes of tree 2.
deg2[3] = 1;
deg2[4] = 1;
}
// Generate random hash values for each node
static void TakeHash(int n, long[] node) {
// Take a very high prime
long p = 97 * 13 * 19;
// Initialize random values to each node
Random rand = new Random();
for (int i = 1; i <= n; ++i) {
// A good random function is chosen for each node
long val = (rand.nextLong() * rand.nextLong() * rand.nextLong())
+ rand.nextLong() * rand.nextLong() + rand.nextLong();
node[i] = val * p * rand.nextLong() + p * 13 * 19 * rand.nextLong() * rand.nextLong() * 101 * p;
p *= p;
p *= p;
}
}
// Return the required answer
static void solve(int n, List<Integer>[] tree1, List<Integer>[] tree2, long[] subtree1, long[] subtree2, long[] deg1,
long[] deg2, long[] 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);
// Count occurrences of hash values for each subtree in both trees
Map<Long, Long> cnt_tree1 = new HashMap<>();
Map<Long, Long> cnt_tree2 = new HashMap<>();
List<Long> values = new ArrayList<>();
for (int i = 1; i <= n; ++i) {
long value1 = subtree1[i];
long value2 = subtree2[i];
// Store the subtree value of tree 1 in a list to compare it later with subtree value of tree 2
values.add(value1);
// Increment the count of hash value for a subtree of a node
cnt_tree1.put(value1, cnt_tree1.getOrDefault(value1, 0L) + 1);
cnt_tree2.put(value2, cnt_tree2.getOrDefault(value2, 0L) + 1);
}
// Stores the sum of all the hash values of children for the root node of subtree 1
long root_tree1 = subtree1[1];
long root_tree2 = subtree2[1];
// Set the count of root hash values to 0
cnt_tree1.put(root_tree1, 0L);
cnt_tree2.put(root_tree2, 0L);
long answer = 0;
for (long x : values) {
// Check if there is any hash value in both trees that matches
if (cnt_tree1.getOrDefault(x, 0L) != 0 && cnt_tree2.getOrDefault(x, 0L) != 0)
++answer;
}
System.out.println(answer);
}
// Driver Code
public static void main(String[] args) {
List<Integer>[] tree1 = new ArrayList[MAX];
List<Integer>[] tree2 = new ArrayList[MAX];
long[] node = new long[MAX];
long[] deg1 = new long[MAX];
long[] deg2 = new long[MAX];
long[] subtree1 = new long[MAX];
long[] subtree2 = new long[MAX];
int n = 6;
// To generate a good random function
Random rand = new Random();
for (int i = 0; i < MAX; i++) {
tree1[i] = new ArrayList<>();
tree2[i] = new ArrayList<>();
}
Insertt(tree1, tree2, deg1, deg2);
TakeHash(n, node);
solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node);
}
}
// Function to check if a node is a leaf node in subtree 1
function isLeaf1(NODE, deg1) {
return deg1[NODE] === 1 && NODE !== 1;
}
// Depth-first search to calculate the hash sum of subtree 1
function dfs3(curr, par, tree1, subtree1, deg1, node) {
for (let child of tree1[curr]) {
if (child === par) continue;
dfs3(child, curr, tree1, subtree1, deg1, node);
}
if (isLeaf1(curr, deg1)) {
subtree1[curr] = node[curr];
return;
}
let sum = 0;
for (let child of tree1[curr]) {
sum += subtree1[child];
}
subtree1[curr] = node[curr] + sum;
}
// Function to check if a node is a leaf node in subtree 2
function isLeaf2(NODE, deg2) {
return deg2[NODE] === 1 && NODE !== 1;
}
// Depth-first search to calculate the hash sum of subtree 2
function dfs4(curr, par, tree2, subtree2, deg2, node) {
for (let child of tree2[curr]) {
if (child === par) continue;
dfs4(child, curr, tree2, subtree2, deg2, node);
}
if (isLeaf2(curr, deg2)) {
subtree2[curr] = node[curr];
return;
}
let sum = 0;
for (let child of tree2[curr]) {
sum += subtree2[child];
}
subtree2[curr] = node[curr] + sum;
}
// Calculates x^y
function exp(x, 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);
}
// Function to build the trees
function insertTrees(tree1, tree2, deg1, deg2) {
tree1[1] = [2];
tree1[2] = [1, 3];
tree1[3] = [2, 4];
tree1[4] = [3, 5];
tree1[5] = [4, 6];
tree1[6] = [5];
deg1[6] = 1;
tree2[1] = [2, 6];
tree2[2] = [1, 3];
tree2[3] = [2];
tree2[4] = [5];
tree2[5] = [4, 6];
tree2[6] = [1, 5];
deg2[3] = 1;
deg2[4] = 1;
}
// Function to generate hash values
function takeHash(n, node) {
let p = 97 * 13 * 19;
for (let i = 1; i <= n; ++i) {
let val = (Math.random() * Math.random() * Math.random())
+ Math.random() * Math.random() + Math.random();
node[i] = val * p * Math.random() + p * 13 * 19 * Math.random() * Math.random() * 101 * p;
p *= p;
p *= p;
}
}
// Function to solve the problem
function solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node) {
dfs3(1, 0, tree1, subtree1, deg1, node);
dfs4(1, 0, tree2, subtree2, deg2, node);
let cnt_tree1 = {}, cnt_tree2 = {};
let values = [];
for (let i = 1; i <= n; ++i) {
let value1 = subtree1[i];
let value2 = subtree2[i];
values.push(value1);
if (!cnt_tree1[value1]) cnt_tree1[value1] = 0;
if (!cnt_tree2[value2]) cnt_tree2[value2] = 0;
cnt_tree1[value1]++;
cnt_tree2[value2]++;
}
let root_tree1 = subtree1[1];
let root_tree2 = subtree2[1];
cnt_tree1[root_tree1] = 0;
cnt_tree2[root_tree2] = 0;
let answer = 0;
for (let x of values) {
if (cnt_tree1[x] && cnt_tree2[x]) answer++;
}
console.log(answer);
}
// Main function
function main() {
const MAX = 300005;
let tree1 = Array(MAX), tree2 = Array(MAX);
let node = Array(MAX), deg1 = Array(MAX), deg2 = Array(MAX);
let subtree1 = Array(MAX), subtree2 = Array(MAX);
let n = 6;
insertTrees(tree1, tree2, deg1, deg2);
takeHash(n, node);
solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node);
}
// Run the main function
main();
import random
from collections import defaultdict
# Function to check if a node is a leaf node
def leaf(NODE, deg):
return deg[NODE] == 1 and NODE != 1
# DFS to calculate hash sum for subtree 1
def dfs1(curr, par, tree, subtree, deg, node):
for child in tree[curr]:
if child == par:
continue
dfs1(child, curr, tree, subtree, deg, node)
# If leaf node, hash sum is same as node's hash value
if leaf(curr, deg):
subtree[curr] = node[curr]
return
# Calculate hash sum of all children
sum_children = sum(subtree[child] for child in tree[curr])
subtree[curr] = node[curr] + sum_children
# Function to calculate hash sum for subtree 2
def dfs2(curr, par, tree, subtree, deg, node):
for child in tree[curr]:
if child == par:
continue
dfs2(child, curr, tree, subtree, deg, node)
# If leaf node, hash sum is same as node's hash value
if leaf(curr, deg):
subtree[curr] = node[curr]
return
# Calculate hash sum of all children
sum_children = sum(subtree[child] for child in tree[curr])
subtree[curr] = node[curr] + sum_children
# Calculates x^y in logN time
def exp(x, y):
if y == 0:
return 1
elif y & 1:
return x * exp(x, y // 2) * exp(x, y // 2)
else:
return exp(x, y // 2) * exp(x, y // 2)
# Helper function to build trees
def build_trees(tree1, tree2, deg1, deg2):
# Building Tree 1
edges_tree1 = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
for u, v in edges_tree1:
tree1[u].append(v)
tree1[v].append(u)
deg1[6] = 1 # 6 is a leaf node for tree 1
# Building Tree 2
edges_tree2 = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 4)]
for u, v in edges_tree2:
tree2[u].append(v)
tree2[v].append(u)
deg2[3] = 1 # 3 is a leaf node for tree 2
deg2[4] = 1 # 4 is a leaf node for tree 2
# Function to assign random hash values to nodes
def assign_hash_values(n, node):
p = 97 * 13 * 19 # A very high prime
for i in range(1, n + 1):
val = (random.randint(0, 10000) * random.randint(0, 10000) * random.randint(0, 10000)) \
+ random.randint(0, 10000) * random.randint(0, 10000) + random.randint(0, 10000)
node[i] = val * p * random.randint(0, 10000) + p * 13 * 19 * random.randint(0, 10000) * random.randint(0, 10000) * 101 * p
p *= p
p *= p
# Function to solve the problem
def solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node):
# Do DFS on both trees to get subtree[x] for each node
dfs1(1, 0, tree1, subtree1, deg1, node)
dfs2(1, 0, tree2, subtree2, deg2, node)
# Count hash values for each subtree of both trees
cnt_tree1 = defaultdict(int)
cnt_tree2 = defaultdict(int)
values = []
for i in range(1, n + 1):
value1 = subtree1[i]
value2 = subtree2[i]
values.append(value1)
cnt_tree1[value1] += 1
cnt_tree2[value2] += 1
# Stores the sum of all the hash values of children for root node of subtree 1.
root_tree1 = subtree1[1]
root_tree2 = subtree2[1]
cnt_tree1[root_tree1] = 0
cnt_tree2[root_tree2] = 0
# Count the number of equal hash values in both trees
answer = sum(1 for x in values if cnt_tree1[x] != 0 and cnt_tree2[x] != 0)
print(answer)
# Main function
def main():
n = 6
tree1 = [[] for _ in range(n + 1)]
tree2 = [[] for _ in range(n + 1)]
deg1 = [0] * (n + 1)
deg2 = [0] * (n + 1)
subtree1 = [0] * (n + 1)
subtree2 = [0] * (n + 1)
node = [0] * (n + 1)
# To generate a good random function
random.seed()
build_trees(tree1, tree2, deg1, deg2)
assign_hash_values(n, node)
solve(n, tree1, tree2, subtree1, subtree2, deg1, deg2, node)
if __name__ == "__main__":
main()
Output
1
Time Complexity : O(N)
Contact Us