Partition the state, Codechef Debugging external contest.

solution.cpp

// Author : MrTwinkleSharma

#include<climits>
#include<iostream>
using namespace std;
const int N = 200010;
int children[N],
nextChild[N],
cumulativeResourcesOfCity[N],
resourcesPerCity[N], toCity[N],
fromCity[N];
void depthFirstTracing(int node, int parent) {
cumulativeResourcesOfCity[node] = resourcesPerCity[node];
for(
int indexOfChildNode = children[node];
indexOfChildNode >= 0;
indexOfChildNode = nextChild[indexOfChildNode]
){
if (toCity[indexOfChildNode] == parent) continue;
depthFirstTracing(toCity[indexOfChildNode], node);
cumulativeResourcesOfCity[node] +=
cumulativeResourcesOfCity[toCity[indexOfChildNode]];
}
}
int main() {
//This n Denotes Number of cities//
int n;
cin>>n;
for (int i = 0; i < n; i++) cin>>resourcesPerCity[i];
for (int i = 0; i < n - 1; i++) {
cin>>fromCity[i]>>toCity[i];
--fromCity[i];
--toCity[i];
fromCity[i + n - 1] = toCity[i];
toCity[i + n - 1] = fromCity[i];
}
for (int i = 0; i < n; i++) children[i] = -1;
for (int i = 0; i < n + n - 2; i++) {
nextChild[i] = children[fromCity[i]];
children[fromCity[i]] = i;
}
depthFirstTracing(0, -1);
int finalAnswer = INT_MAX;
int totalResources = cumulativeResourcesOfCity[0];
for (int i = 1; i < n; i++) {
int cumulativeResourcesOfOnePart = cumulativeResourcesOfCity[i];
int relativeDifference = totalResources - 2 * cumulativeResourcesOfOnePart;
if (relativeDifference < 0) relativeDifference = -relativeDifference;
if (finalAnswer > relativeDifference) finalAnswer = relativeDifference;
}
cout<<finalAnswer;
return 0;
}