Во-первых, это не псевдоэлементы, а псевдоклассы. Их может быть много, но любой псевдокласс применяется к тому элементу, для которого написан.
Во-вторых, :not() в CSS Selectors 3 и большинстве браузеров принимает только простой селектор (т.е. либо один тег, либо один класс, либо один псевдокласс, либо один id). Сложные селекторы в :not() появились только в CSS Selectors 4 и работают пока только в Safari 9+.
Смысл записи .q1 li:first-child .q2 li:hover:not(.q77 li) я понимаю как "элемент li под курсором, находящийся где угодно внутри элемента с классом q2, находящегося где угодно внутри первого элемента li где угодно внутри элемента с классом q1, и при этом не имеющего предка с классом q77". Для частного случая в примере, когда .q77 появляется внутри .q2 (т.е. стиль должен применяться к любым li внутри .q2, кроме ), можно сделать что-то типа такого:
.q1 li:first-child .q2 > li:hover, .q1 li:first-child .q2 :not(.q77) li:hover {
/* стили для li непосредственно в .q2 или через любые прослойки, кроме .q77 */
Если же обертка с классом .q77 может быть где угодно на любом уровне, то всё сложно. Нужно или явно перечислить все возможные варианты вложенности с ее участием, или вообще сделать иначе. Например, искусственно поднять специфичность подобным хаком:
.q77 li:not(#non-existent-ID) { /* хак для поднятия специфичности выше любой комбинации классов, но ниже !important */
/* переопределяем обратно на обычные стили для li */
}
Но еще лучше по возможности не привязываться ко вложенности тегов вообще. Тем более тут всё равно ведь для каждого уровня меню задействован свой класс.