We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Cut the Tree
  5. Discussions

Cut the Tree

Sort by

recency

|

164 Discussions

|

  • 2k23_cscys231212
     + 0 comments
    #include<iostream>
#include<vector>
#include<climits>
using namespace std;

int value[100001], n, tot, best;
vector<vector<int> > v;
bool visited[100001];
int sum[100001];

int dfs(int node)
{
    int ret = 0;
    visited[node] = true;
    int sz = (int)v[node].size();
    for (int i = 0; i < sz; i++)
    {
        int next = v[node][i];
        if (!visited[next])
            ret += dfs(next);
    }
    return sum[node] = value[node] + ret;
}

int main()
{
    best = INT_MAX;
    tot = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> value[i];
        tot += value[i];
    }
    v.resize(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (abs(tot - sum[i] - sum[i]) < best)
            best = abs(tot - sum[i] - sum[i]);
    cout << best << endl;
    return 0;
}

  • mss2518
     + 3 comments

    We can make a mapping of each node, to the sum of their tree. In this case, the root node has a sum equal to the entire tree, and each other node the respective cost of their subtree.

    If we cut at an edge, we spawn two subtrees: one where we just cut (with a sum equal to the mapping of that node) and a 'bigger' tree, with sum equal to the entire tree (i.e., mapping[1]) - the tree we just removed. With this idea, we can map each node to the sum of its tree in O(V + E), and then cut every edge once, perfoming the check in O(1), giving a further O(V + E).

    The total time complexity then becomes O(V + E), with O(V + E) space, too.

    def cutTheTree(data, edges):
    # Write your code here
    adj = collections.defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        
    lookup = {}
    
    def treeSum(node, par):
        if node is None:
            return 0
        if node in lookup:
            return lookup[node]
        ans = data[node - 1]
        for ch in adj[node]:
            if ch == par:
                continue
            ans += treeSum(ch, node)
        lookup[node] = ans
        return ans
    
    treeSum(1, 1)
    minDiff = float("inf")
    def minPart(node, par):
        nonlocal minDiff
        if node is None:
            return
        for ch in adj[node]:
            if ch == par:
                continue
            # cut at child
            tree1 = lookup[ch]
            tree2 = lookup[1] - tree1
            diff = abs(tree1 - tree2)
            minDiff = min(minDiff, diff)
            minPart(ch, node)
    minPart(1, 1)
    return minDiff

  • 2101640100165_CS
     + 2 comments
    class Result {

static List<List<Integer>> graph;
static List<Integer> data;
static int root,res,total;
public static void create(List<List<Integer>> edges, int n){
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Integer>()); // Change to LinkedList<Integer>()
}

for(List<Integer> e : edges) {
graph.get(e.get(0)).add(e.get(1));
graph.get(e.get(1)).add(e.get(0));
}


}

private static int dfs(int r, boolean[] vis){
vis[r]=true;
if(graph.get(r).size() == 0) return 0;

int sum =0;
for(int i : graph.get(r)){
if(!vis[i])
sum+=dfs(i,vis);
}

sum+=data.get(r-1);
res=Math.min(res,Math.abs(total-sum*2));
return sum;


} 
public static int cutTheTree(List<Integer> data, List<List<Integer>> edges) {
// Write your code here
int s = 0;
graph = new ArrayList<>();
root =-1;
res =Integer.MAX_VALUE;
for(int i : data)
s+=i;
total = s;
create(edges,data.size());
Result.data = data;
int v =dfs(1,new boolean[data.size()+2]);
return res;
        
        

    }

}

  • shreyavishwalin1
     + 0 comments
    #include<iostream>
#include<vector>
#include<climits>
using namespace std;

int value[100001], n, tot, best;
vector<vector<int> > v;
bool visited[100001];
int sum[100001];

int dfs(int node)
{
    int ret = 0;
    visited[node] = true;
    int sz = (int)v[node].size();
    for (int i = 0; i < sz; i++)
    {
        int next = v[node][i];
        if (!visited[next])
            ret += dfs(next);
    }
    return sum[node] = value[node] + ret;
}

int main()
{
    best = INT_MAX;
    tot = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> value[i];
        tot += value[i];
    }
    v.resize(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (abs(tot - sum[i] - sum[i]) < best)
            best = abs(tot - sum[i] - sum[i]);
    cout << best << endl;
    return 0;
}

  • gtai_quant
     + 0 comments

    Refined Version without building Node class

    from collections import defaultdict, deque

def cutTheTree(data, edges):
    # Create an adjacency list to represent the tree
    node = defaultdict(set)
    for a, b in edges:
        node[a].add(b)
        node[b].add(a)

    n = len(data)
    subtree_sums = [None] * (n + 1)
    
    # Perform DFS to calculate subtree sums
    visited = [False] * (n + 1)
    stack = deque([1])
    visited[1] = True
    
    while stack:
        i = stack[-1]
        # Check if any child nodes are unprocessed
        if any(subtree_sums[j] is None for j in node[i]):
            for j in sorted(node[i]):
                if not visited[j]:
                    stack.append(j)
                    visited[j] = True
                else:
                    node[i].remove(j)  # Avoid revisiting parent node
            continue
        # Calculate the subtree sum for node i
        subtree_sums[i] = sum(subtree_sums[j] for j in node[i]) + data[i - 1]
        stack.pop()
    
    # Total sum of all nodes in the tree
    total_sum = subtree_sums[1]
    
    # Find the minimum difference between two parts of the tree
    for i in range(2, n + 1):
        diff = abs(total_sum - 2 * subtree_sums[i])
        min_diff = min(min_diff, diff)
    
    return min_diff