 # Will my code be with in the limits of the contrainsts?

we are given a rooted tree that contains 1 to N nodes. The root of the tree is node 1.
each node has some value assigned to it.
we have to find the divisor power

divisor power = Sigma(D[A[i]) * C(i,A[j]))
D(x) = no of divisor of X for ex D(6) = 4

C(i,A[j]) = no of occurance of A[j] in subrtee of node i
where j is an arbitrary node of subtree i

our task is to find the divisor power of each node
2<=n<=100000
1<=A[i]<=100000
1<=x<=y<n

5
10 10 4 4 12
1 2
2 3
2 4
3 5

out = 34 22 9 3 6
below is my code

``````#include<bits/stdc++.h>
using namespace std;

vector<int> mapper;
int arr;
void findDivisors(int n, long long int *div)
{

for (int i = 1; i <= n; i++) {

for (int j = 1; j * i <= n; j++)
div[i * j]++;
}
}

vector<int> dfs(int node , int par)
{
vector<int>x;
x.push_back(node);
{
if (child != par)
{
vector<int>ans = dfs(child , node);
for (auto i : ans)
x.push_back(i);
}
}
mapper[node] = x;
return x;

}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin);
freopen("output.txt" , "w" , stdout);
#endif
int n;
cin >> n;
long long int *div = new long long int;
int z = 1000006;
findDivisors(z, div);
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
}
int t = n;
n = n - 1;

while (	n--)
{
int x;
int y;
cin >> x >> y;
}
vector<int> x = dfs(1, 0);
// vector<pair<int, int>> temp;

// int c[t + 1];
int **c = new int*[t + 1];
for (int i = 0; i < t + 1; i++)
{
c[i] = new int;
}

// for (int i = 1; i < t; i++)
// {
// 	for (int j = 0; j < 100000; j++)
// 	{
// 		c[i][j] = 0;
// 	}
// }
for (int i = 1; i <= t; i++)
{
// vector<pair<int, int>>x;
for (auto ele : mapper[i])
{
// sum+=(div[ele] * )
// c[i][e] = arr[ele]
c[i][arr[ele]]++;
}
}
// temp[i] = x;
for (int i = 1; i <= t; i++)
{
int sum = 0;
for (auto ele : mapper[i])
{
// cout << arr[ele] << endl;
// cout << div[arr[ele]] << " " << c[i][arr[ele]] << endl;
sum += (div[arr[ele]] * c[i][arr[ele]]);
}
cout << sum << " ";

}
}
``````

I am not that good with complexity and this question was asked to me yesterday for a placement round which is over now i couldnt able to solve it that time but i tried it now and i got the right answer just want to know whether it is within constraints or not
If anyone have better solution please mention

Can you please format the code and provide a link to the question?

it was asked in my placement test on hackerearth

Also how can i edit the code kinda new here

I linked the article. Also if you don’t want to go through it, just enclose the code in ``` .
this changes something like cin >> n to

``````cin >> n
``````

Also, the problem is not visible anymore.

because the contest is closed

I do not think that you need to explicitly calculate the occurrence of each element in the subtree. I assume that you are summing over all i and j. Since D[A[i]] is constant, for a particular i, the second term will always sum up to be the number of nodes in the subtree.
Also, this code will give both TLE and MLE because you are copying the entire vector of subtrees on every call of dfs and also, you have declared an array of size 1e5 * 1e5.

An optimal solution would be to only find the no. of divisors for each node and the number of nodes in its subtree. This would reduce the time and memory complexity to O(n)

what can i do after finding out all the nodes in the subtree?? can you please explain once

also how can i deal with the weight associated with the nodes if i just count the nodes ina subtree

I am sorry. I did not mean counting the nodes. I meant the sum of the weights of the nodes. Start from the leaf nodes and at each step, keep track of the parent. Just keep adding to the weight of the parent once you find out the weight of the subtree of the child. Suppose you have tree like this:
5
1 4
1 3
3 5
3 2
Here the leaf nodes are 4, 5 and 2
Weight of subtree of node 3 = weight of node 2 + weight of node 5.
Weight of subtree of node 1 = weight of node 4 + weight of node 3 + weight of node 2 + weight of node 5. But we have already calculated the weight of node 2 + node 5. So we need not do it again.

Thus, instead of copying the entire vector, we will be done in constant time and memory.

1 Like

Since you are summing over all i and j, you will visit all nodes in the subtree and thus you can compress the second part into a constant time calculation.

Do a dfs from the root to figure out all the leaf nodes. Also, keep track of all the parent of each node. The weight of the subtrees of the leaf nodes will be 0. Now at each step, add the weight of the current node to the weight of its subtree and add this to the weight of its parent’s subtree.
This process will take the worst time when the tree is a perfectly balanced binary tree taking a time of nlogn to calculate the weight of each node’s subtree. You could separately find out all the divisors of the nodes then in linear time figure out the final answer.

basically, use dynamic programming and imply use of memoization

Thanks I understood bro just one doubt how can I found the this part of the question
C(i,A[j])
That is occurance of a(j] in subree of i

``````
int w;
void  dfs(int node , int par)
{
w[node] = arr[node];
// x.push_back(node);
{
if (child != par)
{
dfs(child , node);
w[node] += w[child]
}
// else {
// 	// mapper[child].push_back(node);
// 	w[child] += w[node];
// }
}
return;

}
``````

you mean this??

How can i keep track of frequency of weights in a particular subtree???

Yes for the most part. But do remember to subtract the weight of the current node while multiplying because over here, the w[] contains the weight of the current node as well.

Can you please clarify the question: Do you want to multiply with the weight of each node in the subtree or the occurrence of weight of each node.
In the first case: calculating the total weight of the subtree suffices.
In the second case: Since you are summing over all j, the final count will always come out to be the number of nodes in the subtree and you do not need to explicitly keep track of the weight of each node in the subtree.