Most Chinese prepositions are also verbs. For example:
在: to be (at) (verb), at (preposition)
跟: to follow (verb), with (preposition)
给: to give (verb), to, for (preposition)
For that reason, they do carry their verb features even when acting as prepositions. And for what I've seen since I started studying Chinese, the first verb is always the one that's negated and that's inserted in the V/A-not-V/A structure. Some examples:
(if there are any mistakes in my examples, I'd appreciate if a native speaker could point them out)
As you can see, the "prepositions" are always negated.
You may negate other parts of the sentence, but the "neutral" negation is always negating the first verb in Chinese.
Hope this helps. Cheers