https://www.codechef.com/ENAU2020/problems/ECAUG207

can someone help here please…i am not able to understand the test cases…can anyone explain ?

Thank you in advance

so see bro we are given a tree so lets say i consider the first test case:

```
5
1 2
1 3
2 4
3 5
```

so there is an edge between 1 & 2, 1 & 3 , 2& 4 , 3&5

5<-3<-1->2->4 this is how the graph should like . So lets say I don’t use the special operation before attacking any town , I have to face 5 warriors at a time .

Now if i use the special operation on node 1 then there will be no edge between 1 and 2 , and between 1 and 3 . So in this process I capture node 1 and then there will be two components of graph left i.e 5->3 and 2->4.

So if i attack at 2(because its being now disconnected) I have to face 2 warriors now.

Note : 1 is the optimum node now lets say what if i use special operation on node 2 then

1 and 2 will get disconnected and the graphs remaining are 5<-3<-1 & 2<-4.

So now if i attack at node 3 then i have to face 3 warriors at a time which is not optimum so I should have selected 1 which is like the mid point.

Try to figure out the 2nd test case .If u don’t understand I can help and also whenever u post doubts tag admin and problem setter he can help u with the editorial.

u r welcome bro

@sandeep1103 please share the editorial , i m having difficulty in the implementation. would be a great help

I have but the code which i have is not mine i picked someone’s code and modify that code according to me and then try to understand the test cases. I had picked this code before your wonderful help

#include <bits/stdc++.h>

using namespace std;

int n;

int dfs(vector<vector>&a,vector &vis,int x,int &X,int &W){

int ans=0,num=1;

vis[x]=true;

for(int i:a[x]){

if(!vis[i]){

int tmp=dfs(a,vis,i,X,W);

num+=tmp;

ans=max(ans,tmp);

}

}

ans=max(ans,n-num);

if(ans<W)

X=x,W=ans;

else if(ans==W)

X=min(X,x);

return num;

}

int main(){

int t; cin>>t;

while(t–){

cin>>n;

vector<vector> a(n+1);

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

int X,v;

cin>>X>>v;

a[X].push_back(v);

a[v].push_back(X);

}

vectorvis(n+1,false);

int X=INT_MAX,W=INT_MAX;

dfs(a,vis,1,X,W);

cout<<X<<" "<<W<<endl;

}

return 0;

}

Blockquote

Hey!! bro can you share your approach of Notebook Distribution ques. https://www.codechef.com/ENAU2020/problems/ECAUG205 i am having trouble to implement this.

The question basically asks you to find the centroid of the tree. Centroid of the tree is a node whose subtree size does not exceed N/2 (N being the number of nodes). You can check out my submission here:

https://www.codechef.com/viewsolution/37349513

You can simply binary Search over the answer. Here, have a look at my submission and let me know if you are not able to understand anything.

https://www.codechef.com/viewsolution/37345796

“https://www.codechef.com/viewsolution/37372711”

dp denotes subtree size . let me know if u have any issue.

well as far subtree is involved can u please suggest me some starter problems so it would be easy for me to solve this .Like using dfs i can calculate connected components ,length of each connected component and print the node which is a part of the component and where can i learn this. Please reply @ssrivastava990 ,@harsh0911

Bro there are many blogs over codeforces , just google it -

for questions -

“https://codeforces.com/blog/entry/55274”

wow its really nice thanks for ur help

https://codeforces.com/blog/entry/16221

Great place to learn certain basic algorithms and also practise questions.

To practise, I recommend to apply filters on codeforces and then practise to increase your level, gradually moving on to more complex problems.

https://codeforces.com/problemset?order=BY_RATING_ASC&tags=graphs%2Ctrees%2Cdfs+and+similar

googling skills matters

I used binary search for this problem

Here is my solution : https://www.codechef.com/viewsolution/37366022

And if u want to learn how to apply binary search for problems like this do watch Coden code utube channel’s playlist on binary search.It really helped me a lot.

can you explain your logic ? i know how to use binary search but still i am able to think why we use this .