The Deku Kingdom is an irrational tribe that resides in the core of the swamp. Their paranoid and hasty nature make them appear as hostile to most outsiders. They protect the Kokiri Cog, which is hidden deep in the Forest Temple.
The swamp, once a thriving environment, is now plagued by poisons. The core of the poison is a monster releasing spores into the forest, creating vile creatures and turning innocent Deku Scrubs into vicious Mad Scrubs.
In his paranoia, the Deku King tried to protect himself and the kingdom from the spores. His efforts were futile however and he was exposed to the monster's spores, causing him to act mad. He has sealed up the palace and is ordering the guards to ignore the swamp monsters and just protect him.
The Deku are outraged by this and demand a new king, although some remain loyal. However nobody can do anything since the palace is locked up. The Deku village isn't currently affected by the fungi, but is close to infection.
Link will be tasked with destroying small growths of fungus in and around the Deku Palace.
After he has done enough to help the Deku, he will return to the village to find that many of the Deku are missing and the palace is unlocked. Nooku and Roiko are found asleep on the job. Inside, he encounters Maple, who found a map to the cog. She says, "oops, looks like I left the gate open!" Link finds the Deku have stormed the throne room and are demanding that the king be sacrificed to the Kokiri spirits to appease them.
Link is surrounded by Deku who consider sacrificing him, although those who he helped are on his side. Suddenly, the wall is torn down and swamp monsters swarm in and attack. Link must fight them off and destroy a fungal shoot that had been growing on the palace wall, thereby gaining the trust of the Deku. The prince, inspired by Link's bravery, takes control of the situation. He orders the Deku Butler to grant Link access to the Kokiri forest, along with a gift for his assistance: The boomerang!