022 — Subordinates¶

Source¶

Original source: CSES Problem Set — Tree Algorithms section
Platform: CSES — https://cses.fi/problemset/ (task name: Subordinates)
Topic: trees
Difficulty: Medium
Pattern: Subtree sizes (general tree)
Basic idea inherited from: Adjacency list-এর উপর count_nodes

1. Problem in simple words¶

তোমাকে একটা company-র গঠন দেওয়া আছে — n জন কর্মী, প্রতিজনের (১ নম্বর boss ছাড়া) ঠিক একজন করে সরাসরি boss আছে। এটা আসলে একটা rooted tree, root হলো কর্মী 1। তোমার কাজ: প্রতিজন কর্মীর জন্য বলা যে তার নিচে মোট কতজন subordinate (অধস্তন) আছে — মানে তার subtree-তে নিজেকে বাদ দিয়ে কতগুলো node।

উত্তর হবে nটা সংখ্যা: কর্মী 1, 2, …, n-এর subordinate-সংখ্যা।

boss array (কর্মী 2..5-এর boss): [1, 1, 2, 3]

        1            কর্মী 1-এর নিচে সবাই → 4 জন
       / \
      2   3          2-এর নিচে: 4 → 1 জন; 3-এর নিচে: 5 → 1 জন
      |   |
      4   5          4, 5 leaf → 0 জন

2. Which basic idea does this inherit from?¶

এটা concept.md-র count_nodes idea-র সরাসরি সাধারণীকরণ। binary tree-তে তুমি লিখতে 1 + count(left) + count(right)। এখানে tree general (যেকোনো সংখ্যক child), তাই left/right-এর বদলে একটা children-list-এর উপর loop চলে, আর সব child-এর subtree-size যোগ হয়। subordinate-সংখ্যা মানে subtree-size minus 1 (নিজেকে বাদ দিয়ে)।

3. What is the hidden math or logic?¶

লুকানো logic একটা subtree-size recurrence:

size(u) = 1 + Σ size(c)   for each child c of u
subordinates(u) = size(u) - 1   (নিজেকে বাদ)

মানে: একটা node-এর subtree-size = নিজে (1) + সব child-এর subtree-size-এর যোগফল। একবার DFS-এ নিচ থেকে size উপরে বুদবুদ হয়ে উঠলেই প্রতিজনের answer পাওয়া যায়। এটা একটা postorder কাজ — child শেষ না হলে parent-এর size জানা যায় না।

4. Which data structure is needed?¶

একটা adjacency list (children[u] = u-র সরাসরি অধস্তনদের list), একটা size array (প্রতিজনের subtree-size রাখে), আর recursion / explicit stack। CSES-এ n ২ লক্ষ পর্যন্ত যেতে পারে আর tree একটা লম্বা chain হতে পারে, তাই Python-এ হয় recursion limit বাড়াতে হয়, নয়তো iterative DFS লিখতে হয়।

5. Why this data structure fits¶

General tree-তে child-সংখ্যা যেকোনো কিছু হতে পারে, তাই fixed left/right না — adjacency list নমনীয়ভাবে যত খুশি child ধরে। size array প্রতিটা node-এর উত্তর এক জায়গায় জমায় যাতে শেষে এক লাইনে ছাপা যায়। আর যেহেতু parent-এর উত্তর child-দের উপর নির্ভর করে, DFS (postorder) ঠিক সেই "নিচ আগে, তারপর উপর" ক্রম দেয়।

6. Real-life analogy¶

ভাবো একটা বড় প্রতিষ্ঠানে প্রত্যেক manager-কে বলা হলো: "তোমার পুরো দল কত বড়, রিপোর্ট করো।" সবচেয়ে নিচের কর্মী (যার কেউ নেই) বলে "শুধু আমি, ০ জন অধীনে।" তার manager নিজের সব সরাসরি অধস্তনের রিপোর্ট যোগ করে, নিজেকে ধরে, উপরে পাঠায়। এভাবে নিচ থেকে সংখ্যাগুলো উপরে উঠতে উঠতে CEO-র কাছে পুরো প্রতিষ্ঠানের আকার পৌঁছায়। প্রত্যেকের "আমার অধীনে কতজন" = subtree-size − 1।

7. Visual explanation¶

DFS নিচ থেকে size উপরে তোলে; sub = size − 1:

            1   size=5, sub=4
           / \
   size=2 2   3 size=2   (sub=1 each)
          |   |
   size=1 4   5 size=1   (leaf → sub=0)

8. Example input and output¶

Input : n = 5, boss = [1, 1, 2, 3]   (কর্মী 2..5-এর boss)
Output: 4 1 1 0 0                     (কর্মী 1..5-এর subordinate-সংখ্যা)

Input : n = 1, boss = []             -> Output: 0       (একা CEO)
Input : n = 3, boss = [1, 2]         -> Output: 2 1 0   (chain 1→2→3)
Input : n = 4, boss = [1, 1, 1]      -> Output: 3 0 0 0 (1-এর নিচে তিনজন)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিজন কর্মীর জন্য আলাদা করে একটা DFS/BFS চালিয়ে তার নিচের সব node গুনি।

1) প্রতিটা node u-র জন্য:
2)    u থেকে শুরু করে পুরো subtree ঘোরো (নতুন একটা traversal)
3)    গোনা node − 1 = u-র subordinate
4) n বার এই কাজ

10. Why brute force is slow¶

প্রতিজনের জন্য আলাদা traversal মানে O(n²) — উপরের দিকের node-গুলোর subtree বারবার ঘোরা হয় (CEO-র subtree তো প্রায় পুরো tree, সেটা n বার ঘুরবে)। n = ২ লক্ষ হলে এটা সময়সীমা পেরিয়ে যায়। আসলে একটাই DFS যথেষ্ট: নামার পথে নয়, ফেরার পথে প্রতিটা node তার child-দের জমা size নিয়ে নিজের size একবারেই বানিয়ে নেয়।

11. Key observation¶

মূল observation: একটা node-এর subtree-size পুরোপুরি তার child-দের subtree-size-এর যোগফল + 1। তাই সবার উত্তর একটা মাত্র postorder DFS-এ পাওয়া যায় — যখন এক node-এর সব child শেষ, তখন তার size নিশ্চিতভাবে জানা যায়, আর সেটা parent-এর যোগফলে দান করা যায়।

12. Optimized intuition¶

একটা DFS চালাও root (কর্মী 1) থেকে। প্রতিটা node-এ size = 1 দিয়ে শুরু করো, তারপর প্রতিটা child-এ recurse করে ফেরত আসা size[child] যোগ করো। শেষে subordinates = size - 1। পুরো tree একবার ঘোরা → O(n)। গভীর chain-এ Python-এর recursion limit বাঁচাতে হয় sys.setrecursionlimit বাড়াও, নয়তো একটা explicit stack দিয়ে iterative postorder লেখো।

13. Thinking tweak¶

মোচড়: "প্রতিজনের জন্য আলাদা গোনা" ভাবা বন্ধ করো — একটাই walk যথেষ্ট। ভাবো "নিচ থেকে size উপরে তুলব, প্রত্যেকে শুধু নিজের child-দের যোগফল নেবে।" আর binary থেকে general tree-তে যাওয়া মানে শুধু left/right-এর জায়গায় একটা loop over children — মূল postorder fold একই থাকে।

14. Step-by-step dry run¶

n = 5, boss = [1,1,2,3] → children = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}:

dfs(1): size = 1, এখন child 2 আর 3 লাগবে।
dfs(2): size = 1, child 4 লাগবে। dfs(4): leaf → size 1 ফেরত। তাই size[2] = 1 + 1 = 2।
dfs(3): size = 1, child 5 লাগবে। dfs(5): leaf → size 1। তাই size[3] = 2।
ফিরে size[1] = 1 + size[2] + size[3] = 1 + 2 + 2 = 5।
subordinates = size − 1: [5-1, 2-1, 2-1, 1-1, 1-1] = 4 1 1 0 0।

15. Python solution¶

import sys
from collections import deque


def subordinates(n, boss):
    """boss[i] = কর্মী (i+2)-এর সরাসরি boss; প্রতিজনের subordinate-সংখ্যা ফেরত দেয়।"""
    children = [[] for _ in range(n + 1)]   # 1-indexed
    for i, b in enumerate(boss):            # কর্মী i+2-এর boss = b
        children[b].append(i + 2)

    size = [0] * (n + 1)

    # iterative postorder (গভীর chain-এ recursion limit এড়াতে)
    order, stack = [], [1]
    while stack:                            # প্রথমে একটা topological/visit order বানাও
        u = stack.pop()
        order.append(u)
        for c in children[u]:
            stack.append(c)

    for u in reversed(order):               # পাতা→root ক্রমে size জমাও
        size[u] = 1
        for c in children[u]:
            size[u] += size[c]

    return [size[u] - 1 for u in range(1, n + 1)]   # নিজেকে বাদ


# ---- tests ----
assert subordinates(5, [1, 1, 2, 3]) == [4, 1, 1, 0, 0]
assert subordinates(1, []) == [0]                 # একা CEO
assert subordinates(3, [1, 2]) == [2, 1, 0]       # chain 1→2→3
assert subordinates(4, [1, 1, 1]) == [3, 0, 0, 0] # 1-এর নিচে তিনজন

# গভীর chain (recursion limit এড়ানো হয়েছে কি না যাচাই): 1→2→...→1000
deep = list(range(1, 1000))                        # boss[i] = i+1 মানে কর্মী i+2-র boss i+1
assert subordinates(1000, deep)[0] == 999          # root-এর নিচে বাকি সবাই
assert subordinates(1000, deep)[-1] == 0           # সবচেয়ে নিচের জন leaf
print("সব test pass!")

16. Line-by-line code explanation¶

children = [[] for _ in range(n + 1)] — 1-indexed adjacency list; index 0 ব্যবহার হয় না।
for i, b in enumerate(boss): children[b].append(i + 2) — কর্মী i+2-কে তার boss b-র child হিসেবে যোগ করো (boss list কর্মী 2 থেকে শুরু)।
order, stack = [], [1] ... — root থেকে একটা iterative DFS দিয়ে একটা visit-order বানাই (recursion ছাড়া, যাতে গভীর tree-তে stack overflow না হয়)।
for u in reversed(order): — সেই order উল্টে চললে প্রতিটা parent-এর আগেই তার সব child আসে; তাই এটা একটা বৈধ postorder।
size[u] = 1; for c in children[u]: size[u] += size[c] — নিজে 1, সাথে সব child-এর জমা size — subtree-size তৈরি।
return [size[u] - 1 ...] — subordinate = subtree-size − 1 (নিজেকে বাদ)।

17. Output walkthrough¶

subordinates(5, [1,1,2,3]) ওই ছবির tree-তে [4,1,1,0,0] দেয় — assert pass। একা CEO দেয় [0], chain 1→2→3 দেয় [2,1,0], এক root-তিন child দেয় [3,0,0,0]। গভীর 1000-node chain-এও recursion ছাড়া চলে: root-এর 999, সবচেয়ে নিচের 0 — pass। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা node order বানাতে একবার, size জমাতে একবার দেখা হয়; প্রতিটা edge ঠিক একবার করে ব্যবহৃত। n = ২ লক্ষেও দ্রুত।

19. Space complexity¶

O(n) — adjacency list সব edge ধরে (O(n)), size array O(n), আর order/stack O(n)। iterative হওয়ায় recursion call stack-এর O(n) গভীরতা এড়ানো গেছে (skewed tree-তে সেটাই overflow ঘটাত)।

20. Common mistakes¶

recursive DFS ব্যবহার করে গভীর chain-এ RecursionError খাওয়া — CSES-এ tree ২ লক্ষ-লম্বা chain হতে পারে; iterative বা sys.setrecursionlimit লাগে।
subordinate বলতে subtree-size নিজেই ছাপা — নিজেকে বাদ দিতে −1 ভুলে যাওয়া।
1-indexing গুলিয়ে ফেলা: boss list কর্মী 2 থেকে শুরু, তাই boss[i] হলো কর্মী i+2-এর boss।
child শেষ হওয়ার আগে parent-এর size হিসাব করা (ভুল order) — postorder নিশ্চিত করতে হয়।

21. Which basic problem this inherits from¶

ভিত্তি: concept.md-র count_nodes (subtree গোনা) আর Maximum Depth-জাতীয় postorder fold। binary থেকে general tree-তে নিতে শুধু left/right-কে children-list দিয়ে বদলাও; বাকি "নিচ থেকে যোগফল উপরে তোলা" একই।

22. Similar harder problems¶

Tree Diameter (CSES — একই DFS কাঠামোয় height/diameter) — https://cses.fi/problemset/ (এই tracker-এর #25)
Tree Matching (CSES — subtree-তে tree DP, একই adjacency-list DFS) — https://cses.fi/problemset/
Company Queries I (CSES — boss-tree-তে ancestor jump) — https://cses.fi/problemset/

23. Pattern learned¶

Subtree aggregate on a general tree: root থেকে একটা DFS চালাও; প্রতিটা node-এ নিজের value (এখানে 1) দিয়ে শুরু করে সব child-এর জমা মান যোগ করো (postorder)। গভীর CP-tree-তে iterative DFS দিয়ে recursion limit এড়াও। subtree-size / subtree-sum / subtree-count — সব এই একই fold।

24. Final summary¶

ভবিষ্যতের আমাকে: "subtree-size = 1 + সব child-এর size; subordinate = size − 1; একটাই DFS-এ সবার উত্তর।" general tree মানে children-list-এর উপর loop, আর বড় ইনপুটে iterative DFS। 'প্রতিটা node-এর নিচে কতগুলো / কত যোগফল' টাইপ tree problem দেখলেই এই subtree-aggregate চালটা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।