Naruto and One Shot (Graph ques.)
can someone help here please…i am not able to understand the test cases…can anyone explain ?
Thank you in advance :slight_smile:

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

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.:slight_smile:

1 Like

thank you sooooo much @kanisht09 for helping me :slight_smile: this tutorial is very very helpful for me :innocent:

u r welcome bro :smile:

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

1 Like

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 :sweat_smile:

#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;
for(int i:a[x]){
int tmp=dfs(a,vis,i,X,W);
else if(ans==W)
return num;

int main(){
int t; cin>>t;
vector<vector> a(n+1);
for(int i=1;i<n;i++){
int X,v;
cout<<X<<" "<<W<<endl;
return 0;


Hey!! bro can you share your approach of Notebook Distribution ques. i am having trouble to implement this.

Naruto and one shot

The editorial has been posted.


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:

1 Like

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.
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 -


wow its really nice thanks for ur help :smile:

1 Like
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.

1 Like

googling skills matters :stuck_out_tongue_winking_eye:


I used binary search for this problem
Here is my solution :

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 .

Encoding August 20 Problem Name-Notebook Distribution visit here i had the same problem like u :frowning: