Problem link ও উৎস
- **Original source:** CSES Problem Set — Tree Algorithms section
- **Platform:** CSES —
(task name: Subordinates)
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Subtree sizes (general tree)
- **Basic idea inherited from:** Adjacency list-এর উপর count_nodes
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা company-র গঠন দেওয়া আছে — `n` জন কর্মী, প্রতিজনের (১ নম্বর boss ছাড়া) ঠিক একজন করে সরাসরি boss আছে। এটা আসলে একটা **rooted tree**, root হলো কর্মী 1। তোমার কাজ: প্রতিজন কর্মীর জন্য বলা যে তার নিচে মোট কতজন **subordinate** (অধস্তন) আছে — মানে তার subtree-তে নিজেকে বাদ দিয়ে কতগুলো node।
উত্তর হবে `n`টা সংখ্যা: কর্মী 1, 2, …, n-এর subordinate-সংখ্যা।
```text
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 জন
```
### Input ও output {#8-example-input-and-output}
```text
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-এর নিচে তিনজন)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বড় প্রতিষ্ঠানে প্রত্যেক manager-কে বলা হলো: "তোমার পুরো দল কত বড়, রিপোর্ট করো।" সবচেয়ে নিচের কর্মী (যার কেউ নেই) বলে "শুধু আমি, ০ জন অধীনে।" তার manager নিজের সব সরাসরি অধস্তনের রিপোর্ট যোগ করে, নিজেকে ধরে, উপরে পাঠায়। এভাবে নিচ থেকে সংখ্যাগুলো উপরে উঠতে উঠতে CEO-র কাছে পুরো প্রতিষ্ঠানের আকার পৌঁছায়। প্রত্যেকের "আমার অধীনে কতজন" = subtree-size − 1।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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:
```text
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)** ঠিক সেই "নিচ আগে, তারপর উপর" ক্রম দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিজন কর্মীর জন্য আলাদা করে একটা DFS/BFS চালিয়ে তার নিচের সব node গুনি।
```text
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 একই থাকে।
### ছবিতে বোঝা {#7-visual-explanation}
DFS নিচ থেকে size উপরে তোলে; `sub` = size − 1:
```text
1 size=5, sub=4
/ \
size=2 2 3 size=2 (sub=1 each)
| |
size=1 4 5 size=1 (leaf → sub=0)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n = 5`, `boss = [1,1,2,3]` → `children = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}`:
1. `dfs(1)`: size = 1, এখন child 2 আর 3 লাগবে।
2. `dfs(2)`: size = 1, child 4 লাগবে। `dfs(4)`: leaf → size 1 ফেরত। তাই `size[2] = 1 + 1 = 2`।
3. `dfs(3)`: size = 1, child 5 লাগবে। `dfs(5)`: leaf → size 1। তাই `size[3] = 2`।
4. ফিরে `size[1] = 1 + size[2] + size[3] = 1 + 2 + 2 = 5`।
5. subordinates = size − 1: `[5-1, 2-1, 2-1, 1-1, 1-1]` = **4 1 1 0 0**।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 (নিজেকে বাদ)।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 নিশ্চিত করতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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) —