So like, i spent a few days thinking of a possible way to do this, and one of the ideas that hit me was finding the closest parent of two vertices in O(log n) like it's done in tasks 1329 or 1471; in a case of this task, we can quickly find a parent of previous train and current train — a particular turnout that we need to switch, ignoring a potentially huge number of turnouts before this one. We switch it, make a step forward, and then repeat the algo in a subtree. Or so i thought this ideally would be.

I also use the array that has, for each vertex, the trainroute that was passing by through this vertex last time. More or less, because we can't mark them all anyway, because it won't differ from a brute force then and will lead to TL.

Anyways, i have found a countertest for my program:
6 6
X-L.X.X.X.X
..|.|.|.|.|
S-R-R-R-R-R
..|.|.|.|.|
X-R.X.X.X.F
..........|
X.X.X.X.X.F
|.|.|.|.|.|
L-L-L-L-L-R
|.|.|.|.|.|
X.X.X.X.X.X
5
1 1 4
2 6 3
3 6 5
4 1 3
5 4 3

For which, my bruteforce shows a correct answer
12
2 2 2 F
3 2 3 F
4 2 4 L
5 2 4 F
6 2 3 L
6 2 5 F
7 2 3 F
11 5 5 F
12 5 5 L
12 5 4 F
14 5 5 F
16 5 3 R
, but my "quick" algo doesn't have the 14 5 5 F row.

It'll take too much space explaining fully why this happens, but in short, on a certain subtree it sees the route that went through that spot a bit too much time ago, and falsely assumes that further turnouts are arranged for that route. Which is not fully true.
(here's a final "last visitor" map if it can potentially explain it)
00 00 00 00 00 00
03 04 03 33 33 33
00 00 00 00 00 33
00 00 00 00 00 33
00 00 33 33 35 33
00 00 00 00 00 00

So that makes me wonder, if my idea is right overall (it looked pretty to me at first...) but just my implementation is bad, or is the idea itself is a no-go and i should try something entirely different?
Though quite likely i'll just give up, i spent a bit too many days on this without good outcome...