Improve Query Performance
Running EXPLAIN QUERY PLAN on your query gives this:


0|0|0|SCAN TABLE LEGS AS l
0|0|0|EXECUTE LIST SUBQUERY 1
1|0|5|SEARCH TABLE TRAVELDAYS AS d USING AUTOMATIC PARTIAL COVERING INDEX (Day=? AND Value=?)
1|1|4|SEARCH TABLE TRAINS AS t USING AUTOMATIC COVERING INDEX (TrainDaysUID=?)
1|2|0|SEARCH TABLE LEGS AS l USING AUTOMATIC COVERING INDEX (TrainUID=?)
1|3|1|SEARCH TABLE ROUTES AS r USING INTEGER PRIMARY KEY (rowid=?)
1|4|2|SEARCH TABLE STATIONS AS s1 USING INTEGER PRIMARY KEY (rowid=?)
1|5|3|SEARCH TABLE STATIONS AS s2 USING INTEGER PRIMARY KEY (rowid=?)
1|0|0|USE TEMP B-TREE FOR DISTINCT
0|1|1|SEARCH TABLE ROUTES AS r USING INTEGER PRIMARY KEY (rowid=?)
0|2|2|SEARCH TABLE STATIONS AS s1 USING INTEGER PRIMARY KEY (rowid=?)
0|3|3|SEARCH TABLE STATIONS AS s2 USING INTEGER PRIMARY KEY (rowid=?)


Any "AUTOMATIC" index is an index that SQLite thinks is worth creating temporarily; try this:

CREATE INDEX x1 ON TRAVELDAYS(Day, Value);
CREATE INDEX x2 ON TRAINS(TrainDaysUID);
CREATE INDEX x3 ON LEGS(TrainUID);