The Quest for the Sacred Groves
Time limit1sMemory limit2048 MB
Given a tree on n vertices and a permutation p, count the subarrays of p whose vertices form a connected subgraph of the tree.
- Level
Medium6 of 10
- Topics
- Segment tree, Tree, Implementation
- Solved
- No attempts yet
Background
In the heart of ancient Romania, where dense forests meet towering mountains, lies the enchanted kingdom of Vatra Codrilor. The kingdom is protected by sacred groves, numbered from to , and each grove is watched over by a guardian spirit. The groves are connected by secret paths known only to the wise elders. Formally, the secret paths form a tree.
One night, as the full moon rises, the guardians receive a divine message from the Dacian gods. The message is an ancient scroll with a list . Formally, is a sequence of length in which every number from to appears exactly once. The list gives the order in which the guardians must stand in the final battle.
Task
For each subsegment of the list, if the groves are connected through the secret paths without involving any other groves, the guardians of these groves can meet together and draw on the power of the forest.
Count the number of subsegments with that have this property.
Input
The first line contains an integer ().
Each of the next lines contains two integers and (), denoting an edge of the tree.
The last line contains the distinct integers ().
Output
Print a single integer: the number of subsegments with such that the groves form a connected subgraph.