### DEVol's blog

By DEVol, history, 6 weeks ago,

ll dfs1(int src,int par,vector<int> val,ll dp1[],ll dp2[],int k,vector<vector<int>> adj){
if(dp1[src]!=-1)return dp1[src];
if(val[src]%k==0){
ll ans=0;
if(e!=par){
}
}

dp1[src]=ans+1;
dp2[src]=0;
if(e!=par)
dp2[src]+=((ans-dp1[e])*dp1[e]);
}
dp2[src]/=2;
dp2[src]+=ans;
//  cout << src << " " << dp2[src] << " " << ans << endl;
return dp1[src];
}
else{
dp1[src]=0;
dp2[src]=0;

if(e!=par){
}
}
return dp1[src];
}
}

long long countPairs(int N, vector<vector<int>> Edges, vector<int> Val,int K)
{
ll dp1[N+1];
memset(dp1,-1,sizeof dp1);
for(auto e: Edges){
int u=e[0];
int v=e[1];
}
ll dp2[N+1];
memset(dp2,0,sizeof dp2);

int str=0;
//cout << ans << endl;

for(int i=0;i<N;i++){
str+=dp2[i];
}
return str;
}

I have been trying to solve it but my solution either gives TLE or wrong answer and for this specific solution its TLE, Can anyone please find the error in my code and tell me the right approach. Thanks and regards

• -22

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by DEVol (previous revision, new revision, compare).
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +5 Just count the connected components in which all nodes are divisble by k. And choose any two nodes and that path will contribute to your answer.
 » 6 weeks ago, # |   +3 In this problem, while moving from one vertex to another, you cannot cross a vertex whose value is not divisible by k, so just find all connected parts and add the number of possible pairs in the answer. For example : 7 3 3 9 6 5 3 6 6 1 2 1 3 2 4 4 5 5 6 5 7 In the above testcase the value at 4 is not divisible by k so it divides the graph into 2 connected parts {1, 2, 3} and {5, 6, 7}. Thus answer will be (3 * 2) / 2 + (3 * 2) / 2.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I am unable to find why on adding the call for child for nodes whose val is not divisible by k it results in TLE ? If possible Can u plz share your code.
 » 6 weeks ago, # |   +1 I solve it using simple concept of connecting components. In isvalid condition also check weather the child on which we are going to call dfs is divisible by k or not. Count no of nodes in such components in each dfs call and then res+=count*(count-1)/2My code int k; class Solution { public: void dfs(vector &isvisited,vector graph[],int node,long long &count,vector &Val){ isvisited[node] = true; count+=1; for(int child:graph[node]){ if(!isvisited[child]&&Val[child]%k==0){ dfs(isvisited,graph,child,count,Val); } } } long long countPairs(int N, vector> Edges, vector Val,int K){ // code here vector grap[N+1]; for(int i=0;i isvisited(N+1,false); k = K; long long res = 0; for(int i=0;i
•  » » 6 weeks ago, # ^ |   0 Thanks !
 » 6 weeks ago, # |   0 I solved this problem using DSU.You can see that some nodes have "Value" such that -> Val[node] % K == 0, Hence we observe that we can take any edge that connects node 'u' <-> 'v' where Val[u] % K == 0 AND Val[v] % K == 0.So we simply traverse the 'Edges' vector and see if the above condition holds for 'u' and 'v' then we do :- union_operation(u, v), keep in mind to use "size optimization and path compression for fitting time limit".After making such groups, we can traverse for all nodes [0, N — 1] and get their group leader (by using get_operation(node)), if this leader_node is visited (vis[leader_node] == true) then we shall continue our loopOR Elselet then grpSize = size[leader_node] and mark vis[leader_node] = true (we are visiting this leader for the first time) and we simply pick any 2 nodes from this group (because a path will exist and all nodes shall be atleast divisible by k). So update you "ans" as : ans += (grpSize * (grpSize — 1)) / 2(use long long in c++)
 » 6 weeks ago, # |   0 In the same problem firstly i tried to pass the vectors and variables without reference then it was showing TLE (somehow got AC by many optimisation but time taken-1.98 sec)But when i passed them by reference it resulted in AC (time-0.53sec), can someone please explain why this happened.
•  » » 6 weeks ago, # ^ |   0 If you pass without reference, the compiler makes the copy of all the vectors and variables again all the time you call the function, and hence when the compiler makes the copy of a string/vector of length/size n then that copy is made in O(n)...hence the extra time.Passing by reference is a good practice, it saves time and by reference means that the address of the passed variable will be stored....in the case of vector, it is simply the address of the first element, so you see its O(1).Hope I explained it okay :)
 » 6 weeks ago, # |   -7 gfg bad,downvote
 » 6 weeks ago, # | ← Rev. 3 →   0 vector edges[100005];long long int k;long long int dp[100005];vectorvisited(100005,false);class Solution { public: void dfs(int v,vector &val,long long &ans){ visited[v]=1; unsigned long long int sum = 0; unsigned long long int sum1 = 0; bool flag = true; for(auto x : edges[v]){ if(!visited[x]){ dfs(x,val,ans); flag = false; sum += dp[x]; sum1 += (dp[x]*dp[x]); } } if(flag){ if(val[v]%k)dp[v] = 0; else dp[v] = 1; return ; } if(val[v]%k){ dp[v] = 0; return; } ans += sum; assert((sum*sum - sum1)%2==0); ans += ((sum*sum - sum1)/2); dp[v] += sum + 1; } long long countPairs(int N, vector> Edges, vector Val,int K) { k = K; for(auto x : Edges){ edges[x[0]].push_back(x[1]); edges[x[1]].push_back(x[0]); } // memset(visited,false,sizeof(visited)); memset(dp,0,sizeof(dp)); long long p = 0; dfs(0,Val,p); return p; }};i am trying to making answer using subtree but getting wrong answer please correct me. thanks