aditya_sheth's blog

How to solve this problem efficiently?
By aditya_sheth, history, 5 years ago, In English

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

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well, I think it's solvable in $$$O(N*log^2(N))$$$ using HLD.

For simplicity we'll iterate among nodes from $$$1..N$$$

At each node $$$u$$$ let's divide the task of calculating values in two parts.

  1. For all nodes $$$v$$$ which are in subtree of $$$u$$$.
  2. For all nodes $$$v$$$ which are not in subtree of $$$u$$$.

Let $$$r$$$ be the root of the tree (though it's given that it would be 1 always, but we'll go with this notation from here on). Let $$$cnt[x]$$$ denote number of nodes in subtree of $$$x$$$ which are less than equal to $$$x$$$. Note that since we are iterating from $$$1...N$$$ among nodes, keeping this count should be fairly simple. Let $$$val[x]$$$ denote the given $$$values$$$ at each node.

Part 1 is fairly simple which is given by $$$cnt[u]*val[u]$$$.

Now the part 2 at each node $$$u$$$ is given by for each node $$$v$$$ in path from $$$u$$$ to $$$r$$$,

$$$sum$$$ = $$$cnt[v]*(val[v]-val[parent[v]])$$$

Let $$$a[x]$$$ denote $$$val[x]-val[parent[x]]$$$.

Thus now simply $$$sum$$$ = $$$cnt[v]*a[v]$$$.

hence $$$ans[u]$$$ = $$$sum$$$ + $$$cnt[u]*val[u]$$$

Thus above formulae is a standard range query thing which can be effectively calculated using Segment tree with lazy Propagation. Thus a HLD using Segment tree is enough to answer.

Hence for each Node $$$u$$$, we get the $$$ans[u]$$$ in $$$O(log^2N)$$$ (segment tree and HLD chain Traversal).

There are $$$N$$$ such nodes hence final complexity is $$$O(N*log^2(N))$$$.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Unless I'm mistaken, there's a very simple $$$O(N)$$$ DFS solution. Rough code is below, but the basic idea is to compute the subtree sizes, then perform a DFS. We store a preliminary answer counting the total answer for nodes not in our current subtree, which allows us to compute the answer for each vertex once we visit it. Running dfs(0, 0) after computing subtree sizes (doable through a separate DFS) gives the answer.

int subtreeSize[N]; //Precompute this
ll V[N];
ll ans[N];
vector<vector<int> > children;

void dfs(int v, ll preliminaryAns) {
    ans[v] = preliminaryAns + V[v] * subtreeSize[v];
    for (int nxt : children[v]) {
        dfs(nxt, preliminaryAns + V[v] * (subtreeSize[v] - subtreeSize[nxt]);
    }
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I think you are mistaken. $$$ans[u]$$$ contains contribution from all pairs $$$(u,v)$$$ such that $$$v<u$$$. hence $$$SubtreeSize[]$$$ doesn't contain required info.

    What we need, is that when we are finding answer for some node $$$u$$$, any node in the path from $$$root$$$ to node $$$u$$$ should give us $$$subtreeSize[v] = $$$ those node in subtree of $$$v$$$ which are less than $$$u$$$.

    hence if we follow the code snippet, I don't think we can achieve this by pre-calculating subtreeSize array.

    P.S. If I have mis-understood your approach, kindly elaborate. I am keenly interested to know $$$O(N)$$$ approach for this problem.

    Thanks.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Ahh—-I didn’t notice the i<j condition; my bad! I’ll post again if I have any other ideas, but at first glance, your HLD approach seems like a logical way to deal with this condition.

      → Reply