I would approach this by splitting up the work into two tasks:
- Import the categories and their parent/child relationships first
- Import the entries with a flat listing of categories (just the cities is okay).
The structure of the JSON for importing the categories would be something like this:
[
{
"state": "Florida",
"city": "Key West"
},
{
"state": "Florida",
"city": "Orlando"
},
{
"state": "Florida",
"city": "Jackonsville"
},
{
"state": "Florida",
"city": "Miami"
},
{
"state": "Florida",
"city": "Tampa"
},
{
"state": "Texas",
"city": "Austin"
},
{
"state": "Texas",
"city": "Dallas"
},
{
"state": "Texas",
"city": "San Antonio"
}
]
I know this is redundant but it works better with how Feed Me loops over the category elements and creates the category if it doesn't exist and then assigns the parent if (and creates it if it doesn't exist).
You want the mapping to look something like this:

When you go to import your entries you only need to include a flat listing of the category titles (cities) and then they'll be mapped to parent state.