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
nletters, representing the letters associated to the nodes, and finally
n-1lines, each describing a connection between two nodes.
1 â¤ T â¤ 5
1 â¤ N â¤ 100 000
1 -> x, respectiv
x -> 1(unde
xeste 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.