How to solve this problem efficiently?

Revision en1, by aditya_sheth, 2020-06-03 16:30:39

Brute force solution:

vector<long long> bruteforce_solve
{
	vector<long long> ans;
	for(int j=2;j<=n;j++){
		long long sum=0;
		for(int i=1;i<j;i++)
		{
			//LCA(i,j) returns the least common ancestor of 2 nodes in tree.
			sum+=V[LCA(i,j)];	
			//V[LCA(i,j)] is the value written on node LCA
		}
		ans.push_back(sum);
	}
	return ans;
}

Problem Link

Tags #trees, #dsu on tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aditya_sheth 2020-06-03 16:30:39 468 Initial revision (published)