PROBLEM LINK:
Author: Arjun Jaiswal
Editorialist: Pawan Mishra
Difficulty:
EASY
Prequisites:
DFS,observation
Problem;
Given an undirected tree rooted at node 1. Each member of family represents
node in tree. Every node has to buy some candies equal to number of its descendants plus
one. Then Q queries follow. In each query, an integer will be given denoting value of a node.
You have to tell the factorial of sum of candies bought by descendants of the given node
including the given node itself. As the factorial can be very large, print it with modulo 99991.
Quick explanation:
First, Apply a DFS on this undirected tree starting from root to calculate subtree size of each node including itself and store this in an array A. Then again run a DFS on the tree and calculate total candies in the subtree of a node for each node. Use the precomputed factorial values to output the final
answer. For values above 99990 answer will be 0.
Explanation:
Initially, we need to assign every node a value equal to number of its descendant plus one for itself, which gives number of candies that particular node will have to buy. This can be done by applying a DFS starting from node 1. In this DFS, we have precomputed the subtree size of each node i and store it in A[i].
Now the query asks for “total sum of candies bought by descendants of the given node including itself”, it means that for every node i, we have to calculate (A[i<sub>1</sub>]+A[i<sub>2</sub>]+A[i<sub>3</sub>]+ … + A[i<sub>n</sub>]+A[i]), where i1, i2, i3…in in are descendants of i, which can be done by applying a DFS again on tree.
We have to find the factorial of final value at node. As this value can be very large (10^10 in worst case), even precomputation of factorial is
not possible under given time constraint. But if we observe carefully, we will find that modulo is 99991, thus for the value which is greater equal to 99991, factorial of that value will be zero. And for other value which is less than 99991, We need to precompute the factorial for each value.
Thus for each query, we can find the answer in O(1).
Time complexity:O(n+q)*T
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.