As you know, the statement, you are given a tree, right, and you have an nodes and this tree is
unrooted.
So it's just another tree.
No road.
Cool.
And you all have basically two players, right?
Which are I use and Asheesh.
All right.
Sorry for my Indian problem setters, but I'm not going to use these names.
I'm gonna say Alice and Bob.
It's standard for play, for math games and stuff like that.
Ali symbol.
Right.
So.
Yeah.
Alice and Bob call.
I'm just kidding.
Doesn't matter.
So basically when one of these two players is on the move, it can perform the following thing.
It can select any leaf node and remove it together with the edges which are adjacent to that leaf.
Right.
So, yeah.
And we are given a special node, which is X and the player who will remove the node X is going to win
the game.
Right.
So this is it.
We know the problem.
Let's see how to think about this.
First of all, I have to mention that the problem was really tricky.
I think the problem setter wanted to kind of tree costs with this and less or less than or equal to
1000 because you think like whole 1000.
It should be a dynamic programming or something.
Now it's way, way, way simpler than that.
So tell me if everything's okay.
All right.
A camera is okay.
Cool, cool.
Cool camera.
Okay.
Thanks.
So.
All right.
So he really tried to trick us.
If you see this problem setter, you, you will.
You are a little bit tricky.
So let me move on.
Let's think about this.
Right.
I'm thinking about this problem, and I'm like, okay, if the tree is unrooted and the special this
X, guess what I'm gonna do?
I'm gonna root the tree in X.
That's the first thing that I do.
All right.
It's I rooted.
I have a special note.
That special note is the root.
Simple, right.
Makes sense.
So first thing I do, I root the tree in X.
So I imagine X is the root.
If X is the root.
Obviously this node is going to have sons.
Right.
Cool.
So let's imagine our tree.
So special node x, he's now the root.
Right.
Here is going to have sons.
Right.
Maybe three.
Maybe four.
Maybe five.
Who knows.
Well, I don't care because I'm a simple guy.
I always think about the simplest possible scenario.
So at this point I'm like, hmm, what if X has only one son?
So X has only one son.
Right.
Well, if X has only one son.
Doesn't matter.
What nodes do we have here?
X is basically a leaf.
Right.
So the winner is.
Player one.
OK.
That was simple.
That was too easy.
Let's think about two sons.
Right.
It should be harder with two sons.
Let me control Z controls.
All right, good.
Let's say we have two sons, right?
Cool.
I have two sons.
And of course, the sons have each of them has subtree, subtree and No.
And so on and so forth and yada, yada, yada, yada, yada, yada.
It doesn't really matter.
So what's the thing here?
I have got X, which is not a leaf anymore, but when would it become a leaf.
X is going to become a leaf.
When?
Player one and player to start removing Leafs.
Right.
We remove leaves, we remove, we remove.
Doesn't really matter.
But at some point in this scenario.
So we remove this lives.
Right.
And then we have these free notes.
And the player who is going to move next is going to lose.
Right.
Because he doesn't have a choice.
Right.
So the first thing that I notice is that at some point I'm going to have left the Route X and only two
sons.
And in total, only notes, so I have basically removed each and every other note, and I'm just left
with my two sons.
Whoever is the player that is lucky and is left with this scenario loses.
That's a fact.
So when I have two sons, it's quite simple that if I am player one or if I am player two, I need I
need to put you in this position.
I need to do my moves to play my cards right.
So that you are going to be left with this dream.
So how do I do that?
Well, if I want to do this and my opponent wants to do that.
It's quite intuitive what's going to happen, right?
When we have only two sons, we are basically removing leaves.
Doesn't matter in what order.
All right.
It it doesn't matter that I remove this leaf and then he removes this one and then this one and then
this one.
It doesn't really matter.
All that matters is that.
No matter the order, we are going to take turns and remove these leaves until we are left with this
scenario.
So the fingers, the number of nodes is end, right?
The number of total nodes and the nodes X.
First son of X, second son of X.
These are locked.
Right.
These are going to be the notes that are going to removed or lost.
Right.
So I am left with N minus free notes, which basically you can imagine.
We have a set of M minus free notes.
And we just remove the nodes one by one.
Doesn't really matter which node from which of these sub trees doesn't really matter.
We just pick a remove nodes interns.
Right.
So it's just a matter of and minus three modulo two.
And that's it.
On this example.
On this scenario when I have only two sons, I just need to take a look at and minus three modulo two
if N minus three is even.
Right.
Let's say N minus three more gelo two equals zero.
Right.
All right.
Let's imagine I have two sons and N minus three.
Let's say it is for free.
Sons here.
One son here.
All right.
Player one.
Player two.
I hope you can see this because my camera, I think, is there, so.
Yeah.
Player one player to player one.
Player two and player one is left with this scenario.
Player one and player two wins.
So if this is even one.
Player two wins.
If this is odd.
Right.
So equal is one player.
One wins.
And this is how you solve this scenario in which you have only two sons.
And then I thinking about, hmm, what's the difference between this scenario and every other scenario?
No difference.
Yeah, you heard me.
No difference.
You can have free four, five, six sons.
There is no difference.
The answer is exactly the same.
The strategy is exactly the same.
Let me explain why it's real simple.
You can imagine that.
So I've got the root X.
I've got two sons.
And then I've got another free sons.
Right.
Each of these sons has some subtree, subtree, subtree, subtree and salvatori.
Right.
All right.
Well, no matter how many nodes are in each of these sub trees, one thing is for sure.
In the end, I am left with this scenario X one note from some sub tree.
I don't know which one.
And another node from another subtree.
I don't know which one, but I don't care.
I don't care.
The thing is that no matter how many sons I have exactly.
Free nodes are going to be locked because player one player to both of them are going to be very careful.
To keep two sons there alive, right?
At least two sons have to be there.
Right.
So if you imagine that.
All right.
If let's suppose these two sons are going to be left at the end.
This means that no matter what other sub trees do I have?
We are going to remove, remove, remove, remove, remove until we are left with free nodes.
So it is exactly the same thing.
Right.
All you need to do is remove, remove, remove, remove, remove, remove.
Until we remain, we've only free nodes.
And who is in that position?
X and two sons loses.
So again, you take N minus free modulo two, right.
So this was it.
It was super, super tricky.
It's accepted.
Yay!
One more.
All I did is the following thing I read and I read k, I read the edges and if X or Y if one of them
is equal to K, I increment the degree of K.
Right.
So I count.
What is the degree of K.
Why do I need that.
Because remember the very, very first case.
Very, very first scenario was when X X was the not yet x o.
I called it K.
Whatever was when the special node is a leaf.
So this is why I count the degree.
Because if the degree is less or equal than one.
So it is a leaf player.
One wins.
So I print.
I use.
Otherwise I just ask.
And minus three, is it even Asheesh.
Else I use.
And that's it.
Right.
So very, very tricky problem.
It was way easier than probably most of us expected.
Right.