struct Vertex {
	int value;
	int max_leaf;
	vector<Vertex*> children;
};

void CountMaxLeaf(Vertex* vertex) {
	if (vertex == NULL) {
		return;
	}
	vertex->max_leaf = 0;
	for (auto child : vertex->children) {
		CountMaxLeaf(child);
		vertex->max_leaf = max(vertex->max_leaf, child->max_leaf);
	}
	vertex->max_leaf += vertex->value;
}

void TransformTree(Vertex* vertex) {
	if (vertex == NULL) {
		return;
	}

	for (auto child : vertex->children) {
		child->value = vertex->max_leaf - vertex->value;
	}

}

void ChangeTree(Vertex* root) {
	CountMaxLeaf(root);
	TransformTree(root);
}