Let's see the source code.
And you're probably have a better idea about this.
Right.
So what I do is that I read and the number of notes.
I read A, B and C, the coast from the node, the initial digit and the final digit.
And then I read each and every edge, X and Y, and I compute the mean a right, which is the minimum
from this node on the chain to the root, which mean a of one which is the root is initially EHV one.
And I start the DFS.
Right.
We have the DFS.
I'm going to go with this greedy approach and pair the notes together.
So at this step I am with Mode and I remember the father.
Right.
Because I don't want to visit the father again.
That's classic.
So and I initialize an array of bad nodes of only two values, zero and zero.
But nodes of zero means.
How many bad nodes I have that are initially zero and needs to be converted to one.
And how many of them I have that are initially one and need to be convert to zero.
Right.
So this is the type one and type two nodes.
Then I try to see if this note is bad.
So if B of no, these not equal to see of node, that means this is a bad node.
Right.
Note so bad nodes of B of node plus plus.
Right.
I increase, I increment the size of that category.
And then I try out each and every son.
If it's equal to the father.
Just continue.
Because I do want to visit the father again.
If not, I compute the meaning of this son.
Which, as I told you, is the minimum between mean a node and the age of the son.
Right.
Pretty basic.
Then I call DFS.
Of son.
With the father note and what these DFS returns is a pair in which the first argument is basically.
As you have seen when I go, we've DFS on a subtree.
I will remain only with nodes of one type.
Right.
So basically, if let's say I had free nodes of Type one and seven of my of Type two, I, I construct
three pairs and they remain three, four nodes of type two.
Right.
So after bearing all the nodes that I can in some subtree, I'm going to remain with some nodes of only
one type.
So I remember in the first value, what is the type either zero or one and how many nodes of that type
I have left in that subtree that I couldn't pair with any other nodes.
Right.
And I just bad nodes of RMI remaining that first plus equals remaining that second.
Right.
I increase the number of bad nodes from that subtree.
And then what I do is that I pick the minimum between bad nodes of zero and bad nodes of one.
And this is the number of pairs that I can construct.
And I increase the answer.
We've two crossed X crossed mean a of node.
So basically I'm in node.
Right.
This is the current node.
I have the sub trees.
And from this subtree, not from all of this sub trees, I remain with some more type one and some type
two.
I construct X pairs and for each pair I be to cross mean a of node.
Because this is the node where I pair those nodes.
Right.
This is the debt LCA of the north.
Right.
And then of course I do.
I decrease bed nodes of zero in on by X if they are above zero.
I return zero zero job done with the subtree.
I don't have any reminder then if Bednarz of zero is greater than zero.
If father is zero.
Answer is minus one.
Otherwise return zeron bednarz of zero.
Else if father is zero.
Answer is minus one.
Return one and Beddows of one.
Right.
So what we do here is that I find out what is the type of the remaining nodes.
And if it is zero, I return zero.
And how many of them are there?
If it is one, I return one.
And how many of them are there?
If I have remaining nodes which weren't paired with anybody.
And I am in the root, which means father equals zero.
This means I should return minus one.
So that's a guess again.
Take an example.
If it is unclear.
Trust me on this kind of problems which are trees and greedy on trees.
You need to use your pen and paper.
And imagine what happens once you do that.
I'm sure it's going to be clear.
But this is basically the main approach.
So you notice that type one and type two have to be of the same size.
Let's call it X.
Then you prove, as I did, that it's always optimal to choose pairs of nodes.
And don't take more than two nodes in the same group.
And you have the proof with the LCAC.
And after you notice that, you greedily pair the nodes.
As I've told you from the leaves, you tried to pair them as soon as possible because the sooner you
pair two nodes.
The minimum age in that LCA is going to be smaller, so the smaller the total cost.
So the optimal solution, right?
That's it.
Called.