An XSLT-1.0 solution is the following. It uses Muenchian Grouping as a method to get unique country values.
EDIT:
To ensure that the element names are valid QNames, I added a translate(...) expression which transforms all spaces in the respective city name or country name to underscores.
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:key name="countries" match="A" use="country" />
<xsl:template match="/*">
<xsl:copy>
<xsl:apply-templates select="node()|@*" />
</xsl:copy>
</xsl:template>
<xsl:template match="text()" />
<xsl:template match="A[generate-id(.) = generate-id(key('countries',country)[1])]">
<xsl:element name="{translate(country,' ','_')}">
<xsl:for-each select="key('countries',country)">
<xsl:element name="{translate(city,' ','_')}">
<xsl:copy-of select="score" />
</xsl:element>
</xsl:for-each>
</xsl:element>
</xsl:template>
</xsl:stylesheet>
The XSLT-2.0 solution is easier, because it can use xsl:for-each-group:
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template match="/*">
<xsl:copy>
<xsl:for-each-group select="A" group-by="country">
<xsl:element name="{translate(current-grouping-key(),' ','_')}">
<xsl:for-each select="current-group()">
<xsl:element name="{translate(city,' ','_')}">
<xsl:copy-of select="score" />
</xsl:element>
</xsl:for-each>
</xsl:element>
</xsl:for-each-group>
</xsl:copy>
</xsl:template>
</xsl:stylesheet>
The output of both approaches is the same:
<?xml version="1.0"?>
<root>
<Italy>
<Rome>
<score>13</score>
</Rome>
<Florence>
<score>14</score>
</Florence>
</Italy>
<France>
<Paris>
<score>20</score>
</Paris>
</France>
</root>