How to solve this problem efficiently?

Правка en1, от 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

Теги #trees, #dsu on tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aditya_sheth 2020-06-03 16:30:39 468 Initial revision (published)