It seems my code is correct - Click Here
But I am getting WA in it, I have also checked the corner case (didn’t consider 1 as the special city).
I ran a BFS and calculated the total energy to reach every node from node 1 and stored it, then took all leaf nodes energies and greedily checked with energies available.
Can anyone point out the mistake. It’ll be really helpful.
My submission : CodeChef: Practical coding for everyone
Can anyone help me with my WA?
I’ve done almost the same except for the final part of the problem. I used DFS to calculate the depths and energies.
Can this problem be solved using Dijkstra algorithm? I mean at first I have to calculated the minimum cost from the capital city to all cities using Dijlsktra… And then find the number of special city then the answer using multiset…
In theory yes, but we use a special characteristic of trees. We can simply do the dfs traversal of a graph because there’s only a single path between every two vertices.
As for the multiset, every leaf occurs only once so you can get away with a simple set or just an array sorted in increasing order and greedily match pilgrims with lowest energy to leaves of smallest distance. 
I had a doubt. Feel free and please do reply.
This is my soln. I got WA and I didn’t have any Run time Errors.
I used dfs in the question and didn’t use bool visited array. Is it one of the correct way to solve? (Note while inserting I inserted unidirectional directional link betn cities).
If possible can someone tell me what was wrong with my code ?
You should add bidirectional edges in your graph, since input can be given as:
1 3
2 3
In your case you won’t consider 3 - 2 as an edge, meaning you’ll consider 3 as a leaf rather than 2.
This introduces a new issue in your code which is dfs without visited array. You still don’t need visited array, but need a way to tell whether the vertex u is parent of v. This can be solved by introducing parent variable in the dfs defintion.
Also in your later while loop you’ll need a way to break out of the loop once j reaches its maximum value, not only i, because there could be fewer leaves than pilgrims.
I believe this should fix all the issues.
Hey anyone here please check my code which getting WA but i think my approach is right and also i considered all the corner cases CodeChef: Practical coding for everyone
hey aadiupadhyay please check my code which getting WA but i think my approach is right and also i considered all the corner cases Solution: 45071706 | CodeChef
Woohooo !!! Thanks a lot man this clear lots of my doubts… Actually I used this method of unidirectional and no visited array CSES trees section few problems. But after seeing Karik baiyas soln on youtube, I came to know about this parent thing. But I was unable to tell what was wrong with my method.
Thanks for all clarification.
#include<bits/stdc++.h>
using namespace std;
// finding bug # free time
#define int long long int
#define endl “\n”
#define freopen freopen(“input.txt”,“r”,stdin);freopen(“output1.txt”,“w”,stdout);
#define pb push_back
vector<pair<int,int>>adj[100004];
vectorspecial,visit(100004,0);
int dfs(int n,int dist,int cnt)
{
for(auto x:adj[n])
{
int node=x.first;
int wt=x.second;
int d=cnt*wt;
d+=dist;
if(visit[node]==0)
{
visit[node]=1;
dfs(node,d,cnt+1);
}
}
if(adj[n].size()==1 && n!=1)
{
special.pb(dist);
}
}
main()
{
// freopen
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
visit.clear();
special.clear();
for(int i=0;i<100004;i++)adj[i].clear();
int a[m+1];
for(int i=0;i<m;i++)cin>>a[i];
int u,v,w;
for(int i=0;i<n-1;i++)
{
cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
visit[1]=1;
for(int i=2;i<100004;i++)visit[i]=0;
dfs(1,0,1);
sort(special.begin(),special.end());
sort(a,a+m);
// for(auto x:special){assert(x>0);}
int sz=special.size();
int worker=0,home=0;
int ans=0;
vector<int>vi(m+1,0);
for(int i=0;i<sz;i++)
{
for(int j=0;j<m;j++)
{
if(a[j]>=special[i] && vi[j]==0)
{
ans++;
vi[j]=1;
break;
}
}
}
cout<<ans<<endl;
}
}
I did the same thing as the editorial says but it gave me WA.
Can anyone tell me what is wrong with my [submission ]CodeChef: Practical coding for everyone
Thanks man!
Hey! can you please explain just one thing… how did you realize that there exists only a single path between two vertices? is it because there are N-1 edges?
There must exist at least one path between every pair of vertices (u, v) according to the statement of the problem.
Now suppose there exists more than one path between vertices u and v. This means there are k paths between them, such that k \geq 2.
Since k \geq 2, there are 2 different paths we can shoose p and q. If this were true there would exist a cycle (formed by unique vertices of p and q), which by the definition of tree is impossible. So we derive a contradiction, this by combining the first and second statement we conclude there must be one and only one path between two vertices of a tree.
Yes because it is given cities are connected in the form of tree and tree is acyclic graph so there will always be a unique between two vertices.
I don’t get what I’m doing wrong can someone help ? CodeChef: Practical coding for everyone Here’s the solution.
Also, I’m quite new to graph problems any good resources that you guys would recommend?
@zephxr @aadiupadhyay plz help, getting TLE but approach is right and within the constraints
Solution: 45098841 | CodeChef
Your approach is correct, but TLE is coming because you are storing the tree in a 2D matrix, which is taking much space(10^5 * 10^5) and time(10^5 * 10^5).In the DFS function, you are iterating all other nodes for each node (Line:7), so time is (10^5 * 10^5).For more information, you can visit this website, where they have discussed the Time complexity of DFS in detail - Click Here
If you store the tree in an adjacency list, then your time complexity will reduce to O(V+E) = O(10^5 + (10^5-1)) which is O(10^5 + 10^5)
You can visit the above-mentioned line, it will give more clarity.
Thanks alot, i understood its better to make adjacency list. I used to avoid it as a common query could be, whether there’s an edge from A to B ?, So we could answer it in O(1) in matrix, instead of list.