Corporate Skill Diversity

Easy

0/40

0 upvote

Problem statement

You are an HR analyst at a large corporation. The company's organizational structure is a tree, with the CEO at the root. Each employee is a node, and a direct report relationship is an edge. Every employee has been tagged with a primary "skill ID," an integer representing their main expertise.

Your task is to answer a series of queries from management. For any given manager u in the company, they want to know the skill diversity of their team. The skill diversity is defined as the number of unique skills present among that manager and all the employees who directly or indirectly report to them (i.e., their entire subtree).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer N, the number of employees (nodes).

The next N-1 lines each contain two integers u and v, representing a reporting line between employee u and v.

The next line contains N space-separated integers, where the i-th integer is the skill ID for employee i+1.

The next line contains an integer Q, the number of queries.

The next Q lines each contain a single integer u, the manager for whom to calculate skill diversity.

Output Format:

For each query, print a single integer on a new line representing the count of distinct skills in the queried manager's subtree.

Note:

The tree is rooted at node 1.

The subtree of an employee u includes u themselves, their direct reports, their reports' reports, and so on.

Sample Input 1:

7
1 2
1 3
2 4
2 5
3 6
3 7
10 20 30 20 40 30 50
3
1
2
6

Sample Output 1:

5
2
1

Explanation for Sample 1:

Query for node 1:
- Subtree: The subtree rooted at node 1 includes all nodes in the tree: {1, 2, 3, 4, 5, 6, 7}.
- Values in Subtree: The corresponding skill IDs for these nodes are {10, 20, 30, 20, 40, 30, 50}.
- Distinct Values: The set of unique skill IDs is {10, 20, 30, 40, 50}.
- Count: The size of this set is 5.

Query for node 2:
- Subtree: The subtree rooted at node 2 includes node 2 and its descendants, {4, 5}. The full subtree is {2, 4, 5}.
- Values in Subtree: The corresponding skill IDs are {20, 20, 40}.
- Distinct Values: The set of unique skill IDs is {20, 40}.
- Count: The size of this set is 2.

Query for node 6:
- Subtree: Node 6 is a leaf node, so its subtree contains only itself: {6}.
- Values in Subtree: The corresponding skill ID is {30}.
- Distinct Values: The set of unique skill IDs is {30}.
- Count: The size of this set is 1.

Expected Time Complexity:

The expected time complexity is O((N+Q) log N). A naive solution of running a separate DFS for each query would be O(Q * N), which is too slow.

Constraints:

1 <= N, Q <= 10^5
1 <= skill_id <= 10^9

Time limit: 2 sec

Approaches (1)

Approach 1

DFS with Small-to-Large Merging

Time Complexity

Space Complexity

(100% EXP penalty)

Corporate Skill Diversity

Console