Algorithms Thread Episode 8: Tree Basics

Really appreciate your effort for helping beginners to learn new concepts and improve!

Looking forward to it!

SecondThread orz

Wait..... How come this is on the frontpage of CF?

Errichto and Thread are changing the learning game istg.

At this point, since everything's already prepared for it, they might as well add your stuff to EDU

Spreading CP knowledge!

Thanks, we will try our best to learn new and interesting concepts.

Loved the new format ! This helps gain much more confidence in the covered than just watching a tutorial on some topic and not getting custom problems on that topic.

Thanks, that’s exactly what I need.

The gym problems are very nice for reaffirming one's understanding of tree basics!

For problem D, what was the offline solution you had in mind? The text at the top implies that there exists an offline solution that's simpler than the online solution, but the only thing I could think of is some wack dfs + segtree solution where you update the answer for a query whenever you reach one of its endpoints. That seems way too complicated to warrant explicitly disallowing offline solutions lol.

I really love your content

Your screencast(s) are really helpful.

Please give any hints for second problem.

Dear SecondThread,

Thank you for all the hard work you put in daily! Know that it is recognized and greatly appreciated, It’s an honor for our codeforces community to have someone like you.

May you reach every height of success!

Hey nice video,

In the tree shown at 36:11, how can I find the sum over the path starting at the node with input time 3 and the node with input time 13? I can think of a way to do it but it requires calculating LCA of the endpoints, is there a way to do it without LCA?

Can Someone Explain the Samples of Problem F Please

expecting more and more from all of you

thanks SecondThread

The gym-set along with the usual videos format is indeed really nice. Thank you for your hard work.

I've just failed my math exam because of secondthread, he says that pi = 3 in 102694A - Circumference of a Tree, so I used pi = 3 to calculate the volume of a sphere and I got 0 marks on that problem. Guys, don't trust secondthread.

A bit off topic, but can we expect a video on round 1 problems of hackercup, SecondThread ?

Hey guys, I am bit stuck on prblem B, my approach was:

• start from arbitary node and find the farthest node, call it 'root'
• from 'root' , do a bfs and find the distance of all other nodes
• The maximum distance now will be the diameter,now,
• If distance of some node from 'root' is same as diameter or zero, the answer for this will be diameter+1 , else the answer for this node will be same as diameter

I am getting a wrong answer on test 6. Can someone plz help?

Any general tips to debug will also be appreciated.

This was a wonderful effort . can anyone give me the link for other episodes.

Your screencast are really helpful. Thank You!

1006E - Military Problem
Great problem on one of the concepts explained in the video. Highly recommend it!

My solution for reference: 90223865

Someone give me a hint on E, please

As a beginner, your episode has really taught me a lot about the many application of trees. Thanks a ton for this!

Hey can someone recommend a good list of problems which contains different( hopefully all theory) types of problems on graphs and/or trees....It would be much appreciated....

can someone help me , I am getting memory limit exceeded in B. https://paste.ubuntu.com/p/6B8kdrvkyh/

SecondThread

Any idea for D. Till now , this is how I am going: ( I guess m is always n-1).

• we need to find the minimum valued edge between sources and destination of the flow network, (as its a tree <or I am wrong here?> and only one path is present between any two nodes).
• we can do this by storing values of minimum for 1,2,4,8,16.. jumps above for each node, and find them just like we build the jump array in binary lifting.
• Now we can move to the lca and keep calculating the minimum along both souces to lca and destination to lca, again using the binary lift technique.

Am I going the right way ? ( Wrong answer on 6)

Someone give me a hint on F, please

My 2-dfs calls in B is receiving TLE, is it expected ?

My code for problem B https://ideone.com/dd5gOx with poor English commentary :)

Math burned me, yet again!!

SecondThread

For E the products can be as large as 10^500000 ( that is ((10^5)^(10^5)) ) and we have to store approx 10^6 of those.....how can it be done....can I get a hint?

The problems are really, really good. Even if they use basic concepts they were not actually so easy (at least for me). I found the fifth problem very cool and challenging if you don't have experience using mathematical functions (I didn't until this problem :D). I give all my respects to the creator of this problemset. Thanks for investing your time in helping others.

For question C the code is running on my computer btt it shows runtime error for test case 3

90309168

I haven't registered yet does that mean i'll have to wait for next 12 days?

Hello, i am currently at problem E and i dont understand how does it is not 1.5 in the second example, at the second line.

Since it is 1-rooted, 1 has value 3, 2 has value 2 and 3 has value 1 , no ??? what did i missed here ??

Could anyone please help me with problem E?How to handle such big numbers?

I realy enjoy E, although I've made 17 WA.

Can someone tell me why bfs doesn't work in promlem A to calculate the diameter. It is giving me tle.

Hi, this is my first time solving Tree based problems on CF. I am having trouble understanding how to give the edges so that I can construct a tree. For example in the first question, the test case is

3

3 2

2 1

How will we construct a tree with 3,2 as edges and which node will they belong to? How will we construct a tree with this? I have seen some other solutions using arrays but i can't understand them.

Leetcode does it like this-

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

I have previously solved on LeetCode where we had to just write the function so I am very new to this.

Any hint for problem F? (getting wrong answer)

Thank you very much for this effort. I really liked the problems.

I solved F by observing some examples, can somebody give proof for F, why this works?

Will all the test cases be made public after the contest ends?

I am getting TLE in TC 4. I stretched the tree along the diameter and after that if node is added to the end points of diameter then dynamic diameter will increase by 1 otherwise not. My solution is here. Please somebody tell me error in my approach.

1 sec time limit is pretty rough for java?

Can someone please explain me what's wrong in my logic for B ? I seem to be repeatedly failing test case #6.

Can anyone pls provide some test case for problem C? im getting WA on test 4

In question no C these are the arrays in my programm my code is runnig is fine in my system btt shws runtime error when i submit can this be a memory issue??

int N, D;
int depth[300010];//depth of node
vector<int> adj[300010];
int par[20][300010];//binary lifting table

Inside main

    memset(depth, 0, sizeof(depth));
    for (int i = 0; i < 300010; i++)
    {
        adj[i].clear();
    }
    memset(par, -1, sizeof(par));

SecondThread, what's the constraint of q in D?

Thank you very much for the problemset, it's very helpful! I like how it's not just straightforward "implement LCA and be done with it", but includes some modification that forces you to understand the concept behind it.

I have a question about F. It seems that the observation is

Which seems intuitively true, but how to prove it?

I am not able to solve circumference of tree problem .. also there is no editorial available .. what to do ?

It's really helpful! Thank you !