CareerCup

Let us define the notion of 'root' and 'parent' on the tree. Let the root of the tree be 'r'.

Suppose that for every node 'x', we have computed the total weight of the subtree rooted at 'x' (this includes the weight of 'x'). Let us call this sum: S(x).

Then for every edge (u,v) in the tree, where 'u' is the parent of 'v', the sums of the 2 trees formed on removing edge (u,v) are S(v) and S(r) - S(v). In this way, we can iterate over all the edges and return the minimum possible difference.

Time complexity: O(N), space O(N).

We can do it like this..!!!

#include <iostream>
#include <cmath>
using namespace std;

int sum;

struct Node
{
	int id;
	Node *next;
};

struct node
{
	int id;
	int pid;
	node *next;
};

class Queue
{
	private:
		node *head;
		node *tail;
	public:
		Queue()
		{
			head = NULL;
			tail = NULL;
		}
		void insert(int id,int pid)
		{
			node *temp = new node();
			temp->id = id;
			temp->pid = pid;
			temp->next = NULL;
			if(tail)
				tail->next = temp;
			tail = temp;
			if(!head)
				head = temp;
		}
		node* remove()
		{
			node *temp = new node();
			temp = head;
			head = head->next;
			return temp;
		}
		void display()
		{
			node *temp = head;
			if(temp)
			{
				cout<<"("<<temp->id<<","<<temp->pid<<") -> ";
				temp = temp->next;
			}
		}
		bool empty()
		{
			if(head)
				return false;
			else
				return true;
		}
};

class List
{
	private:
		Node *head;
		int weight;
		int id;
	public:
		List()
		{
			head = NULL;
			weight = 0;
			id = 0;
		}
		void setpar(int d,int w)
		{
			id = d;
			weight = w;
		}
		void insert(int a)
		{
			Node *temp = new Node();
			temp->id = a;
			temp->next = head;
			head = temp;
		}
		void cal_sum(int a, Queue *queue)
		{
			sum = sum + weight;
			if(head)
			{
				Node *temp = head;
				while(temp)
				{
					if(temp->id != a)
						queue->insert(temp->id,id);
					temp = temp->next;
				}
			}
		}
};

int main()
{
	Queue queue;
	node *temp = new node();
	int T,N,i,diff,sum1,sum2,w;
	cin>>T;
	while(T--)
	{
		cin>>N;
		int A[N-1],B[N-1];
		List list[N];
		for(i=0;i<N;i++)
		{
			cin>>w;
			list[i].setpar(i,w);
		}
		for(i=0;i<N-1;i++)
		{
			cin>>A[i]>>B[i];
			list[A[i]].insert(B[i]);
			list[B[i]].insert(A[i]);
		}
		diff = -1;
		for(i=0;i<N-1;i++)
		{
			sum = 0;
			queue.insert(A[i],B[i]);
			while(!queue.empty())
			{
				temp = queue.remove();
				list[temp->id].cal_sum(temp->pid,&queue);
			}
			sum1 = sum;
			sum = 0;
			queue.insert(B[i],A[i]);
			while(!queue.empty())
			{
				temp = queue.remove();
				list[temp->id].cal_sum(temp->pid,&queue);
			}
			sum2 = sum;
			if(diff == -1)
				diff = abs(sum1-sum2);
			else if(diff > abs(sum1-sum2))
				diff = abs(sum1-sum2);
		}
		cout<<diff<<endl;
	}

}

here n = 1000 and t = 100, my algorithm takes n^2 time, so here the total it become 10^3*10^3*10^2 = 10^8, can be done in 1 sec. by 10^9 calculation/sec. machine.

This seems like TWO good but unrelated questions. Or, I am I overtired?

it is a BFS question
save the tree as a graph in 2-d matrix or adjacency list form.
calulatemindiff()
{
for each edge
{
apply bfs on left part and then on right par to calculate the sum of its both side tree

calculate the difference of these to sum.

update the global diff accordingly.
}
return globaldiff;
}