You are viewing a single comment's thread. Return to all comments →
class Node { public: int number; int value; Node* parent; vector<Node*> children; Node(int num, int val, Node* par) : number(num), value(val), parent(par) {} }; Node* treeCreator(int n, const vector<vector<int>>& edges, const vector<int>& data) { vector<vector<int>> V(n + 1); for (int i = 0; i < edges.size(); i++) { V[edges[i][0]].push_back(edges[i][1]); V[edges[i][1]].push_back(edges[i][0]); } queue<Node*> Q; Node* root = new Node(1, data[0], NULL); Q.push(root); while (!Q.empty()) { Node* t = Q.front(); for (int i = 0; i < V[t->number].size(); i++) { if (t == root or V[t->number][i] != t->parent->number) { Node* child = new Node(V[t->number][i], data[V[t->number][i]-1], t); t->children.push_back(child); Q.push(child); } } Q.pop(); } return root; } int sum (Node* node, vector<int>& sumArray) { int total = 0; for (Node* T : node->children) { total = total + sum(T, sumArray); } total = total + node->value; sumArray[node->number] = total; return total; } int cutTheTree(vector<int> data, vector<vector<int>> edges) { int n = data.size(); Node* root = treeCreator(n, edges, data); vector<int> sumArray(n+1); sum(root, sumArray); int result = INT_MAX; for (int i=2; i <= n; i++) { result = min(result, abs(sumArray[1] - 2*sumArray[i])); } return result; }
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the Tree
You are viewing a single comment's thread. Return to all comments →