Ukraine crisis: Putin visit to Crimea angers US and EU
The US and EU have condemned President Vladimir Putin's first visit to Crimea since Russia annexed the peninsula from Ukraine in March.
The US state department said the trip was "provocative and unnecessary". The Kiev government called it a "gross violation of Ukraine's sovereignty".
Mr Putin praised Crimea for joining Russia, as he marked the Soviet victory over the Nazis in World War Two.
As he visited, there were deadly new clashes in south-eastern Ukraine.
Ukraine's Interior Minister Arsen Avakov said at least 20 pro-Russian activists and a Ukrainian security officer died in the clashes in the port of Mariupol.
The government said there was a gun battle when pro-Russian activists tried to storm a police HQ.
However, some local witnesses accused the security forces of opening fire on unarmed protesters who had entered the building. Local officials put the casualties at seven dead and 39 injured.
Crimea voted to join Russia in March - in a referendum dismissed by Kiev and the West as illegal.
Pro-Russian separatists in Ukraine's eastern Donetsk and Luhansk regions are planning to hold secession referendums on Sunday.
The separatists remain in control of many official buildings across the east despite a military operation by Kiev to remove them. Dozens have been killed in the unrest.
US State Department spokeswoman Jen Psaki called Mr Putin's trip provocative and unnecessary, adding: "Crimea belongs to Ukraine and we don't recognise of course the illegal and illegitimate steps by Russia in that regard."
US National Security Council spokeswoman Laura Magnuson said the visit "only served to fuel tension".
Maja Kocijancic, a spokeswoman for EU foreign policy chief Catherine Ashton, said the EU "regretted" the presence of Mr Putin at a military parade in Crimea's port of Sevastopol.
"An important day in our shared history, dedicated to honouring the enormous sacrifices and giving remembrance to the millions of dead in the Second World War, should not have been instrumentalised to give visibility to the illegal annexation of Crimea," she said.
Nato's Secretary General Anders Fogh Rasmussen said Mr Putin's visit was "inappropriate".
US Secretary of State John Kerry and Russian counterpart Sergei Lavrov spoke again by telephone on Friday, but both sides later reiterated their stated positions.
Ms Psaki said Russia should tell the separatists to lay down their arms and abandon plans for secessionist referendums.
Russia's foreign ministry said Mr Lavrov had urged the US to influence Kiev to stop its military operations against separatists.
During his visit to Crimea, Mr Putin said the peninsula had shown loyalty to a "historical truth" in choosing to be part of Russia.
He said: "There is a lot of work ahead but we will overcome all difficulties because we are together, which means we have become stronger."
The BBC's Daniel Sandford in Sevastopol says Mr Putin was treated as a conquering hero as he walked through the main square and shook hands with Crimeans.
Mr Putin earlier addressed thousands during a huge military parade in Moscow's Red Square, vowing to defend the "motherland".
Ukraine's interim authorities held a brief veterans' ceremony in Kiev's main park.
The authorities feared pro-Russian activists would try to stoke violence if the celebrations were higher profile.
Nazi Germany invaded the USSR - which included Ukraine - in June 1941. Crimea was put under Ukrainian administration in 1954.