As to be expected, the overwhelming majority of Paleolithic Europeans belonged to paternal lineages that have effectively gone extinct or have been several times superseded. Maternal lineages have mostly suffered from frequency changes because most women who ever lived had offspring.
The most interesting part of the paper is the blue-eyed, dark-skinned man from Villabruna Cave 1, directly dated to about 14,000 years ago and belonging to paternal haplogroup R1b1. He was buried with a bag of implements and covered in red-painted rocks in the Dolomite Mountains.
There's more that is interesting about him than just the y-chromosome, but for a little background see the BBC story...
|Fig 2 LUP burial of Villabruna 1. (Vercellotti et al, 2008)|
So the first interesting thing is that Villabruna man's body proportions are intermediate between modern Europeans and Africans. In fact, he generally clusters with North Africans on several skeletal metrics, although facially he is Caucasian. This doesn't mean he is <North African> and it doesn't mean mixed, but it does suggest some meaningfully deep ancestry in a sufficiently warm climate, possibly the Southern Near East(?).
Genetically, he and his cluster represent a shift towards the Near East from earlier Europeans, and really from the earlier 'true' Gravettians in Eastern Europe. When looking at his physical proportions, Vercellotti et al (2008) seemed to suggest that his long-limbed features were a relict of early AMH or possibly some sort of new response to a warming climate. It now seems migration offers the most plausible explanation for his body type in light of DNA. To be clear though, his cluster extends all over Western Europe even though his unique lineage is so far only seen in Italy.
|Fu et al, 2016|
See also [Maju's post on Ahmarian culture]
Vercellotti, Alciati, Richards, Formicola (2008) "The Late Upper Paleolithic skeleton Villabruna 1 (Italy): a source of data on biology and behavior of a 14.000 year-old hunter" Journal of Anthropological Sciences. Vol. 86 (2008), pp. 143-163 [Link]