Sponsors Gold
...
00:02
00:01
00:00
Time’s up little one… let’s see the code he growled. The suspense was excruciating. I could hear little pearls of sweat drip from my forehead onto the ground. SILENCE. Drip, drip. I felt myself slip into unconsciousness… a bright sunny day… probably a national holiday… the wind caresses the tall grass and the old willow in my parent’s backyard. I was careless back then, free to soar the sky and chase time! My brother had just returned back from his latest mission…he was a soldier. Laughter and smoke from the barbeque filled the air. That smell… wait… my eyes started opening. I was surrounded by flames. Igor must have activated the auto-destruct button from the control panel. I started suffocating on the dense smoke… this was the end. My lungs could not withstand the lack of oxygen and my body started shrivelling up like a raisin. I tried to slither my way towards the emergency escape pit when a flash of light caught the corner of my eye. It was the center screen. Igor must have forgotten about it… pretty sloppy for a grade A terrorist! I gathered all of my strength and dragged my body in that direction. It was a basic map of the world with several red nodes on it. Next to the map there was a huge key… I quickly scanned it for additional information. The nodes were shaped like a giant tree… NB… nuclear bombs! So this was Igor’s demented plan all along? Wiping out civilisation? Each node is labelled from 1 to N. Beneath each number there is one lowercase letter. Connections started appearing in between the nodes… Igor was probably planning detonations. Each detonation route starts with the first node and forms a palindrome out of the lower case letters… the detonation code. Knowing Igor… he’s probably going to choose the longest route for his massive annihilation scheme! What is it about pain that brings joy to people? I suddenly felt very dizzy… the smoke… the flames… they were engulfing everything. If I could figure out the longest route before Igor, I could most probably hack into his detonation panel and stop the entire operation. But time is not on my side… especially since I’ve got about 4 minutes of consciousness left… smoke… grassy plains… free spirits!
You are given a tree with nodes labled from 1 to N. Each nodes contains a lower case letter from the english alphabet. Find the longest palindrome you can form out of all of the nodes starting from the node labled 1.
T, the number of tests.n, the number of nodes, then a line with n letters, representing the letters associated to the nodes, and finally n-1 lines, each describing a connection between two nodes. 1 ≤ T ≤ 51 ≤ N ≤ 100 000| Input | Output |
|---|---|
| 2 5 abada 1 2 2 3 3 4 1 5 5 abbad 1 2 2 3 3 4 1 5 | 3 4 |
1 -> x, respectiv x -> 1 (unde x este nodul curent din parcurgere), daca acestea corespund, probabilitatea ca cele siruri sa difere este foarte mica, mai ales daca nu calculam o singura valoare hash, 2 sau chiar 3 valori hash diferite. Implementarea efectiva o lasam ca tema cititorilor.