Problem link ও উৎস
- **Original source:** CSES Problem Set — Tree Algorithms section
- **Platform:** CSES —
(task name: Tree Diameter)
- **Topic:** trees
- **Difficulty:** Hard
- **Pattern:** Diameter at CP scale
- **Basic idea inherited from:** Diameter of Binary Tree (#18), general tree, deep recursion সামলানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **general tree** দেওয়া আছে — `n`টা node, `n−1`টা edge, কোনো cycle নেই, সব connected। প্রতিটা node-এর যেকোনো সংখ্যক প্রতিবেশী থাকতে পারে। তোমার কাজ: tree-র **diameter** বের করা — মানে যেকোনো দুই node-এর মধ্যে সবচেয়ে লম্বা path-এ কতগুলো **edge** আছে, সেই সর্বোচ্চ সংখ্যা।
এটা LeetCode-এর Diameter (#18)-এর CP-সংস্করণ: গঠন binary নয় (adjacency list দিয়ে আসে), আর `n` ২ লক্ষ পর্যন্ত — তাই গভীর recursion সামলানোটাও সমস্যার অংশ।
```text
edges: 1-2, 1-3, 3-4, 3-5
1
/ \
2 3
/ \
4 5 সবচেয়ে লম্বা path: 2 → 1 → 3 → 4 (বা 5), 3 edge → diameter 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : n = 5, edges = [(1,2),(1,3),(3,4),(3,5)]
Output: 3 (path 2→1→3→4, 3 edge)
Input : n = 1, edges = [] -> Output: 0 (একা node, কোনো edge নেই)
Input : n = 2, edges = [(1,2)] -> Output: 1 (একটামাত্র edge)
Input : n = 4, edges = [(1,2),(2,3),(3,4)] -> Output: 3 (সোজা chain)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা রাস্তা-জালে (গাছের মতো, কোনো লুপ নেই) তুমি সবচেয়ে দূরের দুই শহরের মধ্যে দূরত্ব জানতে চাও। প্রতিটা মোড়ে দাঁড়িয়ে দেখো — এই মোড় থেকে কোন দুই দিকে গেলে সবচেয়ে দূর যাওয়া যায়; সেই দুই দূরত্ব জুড়লে এই মোড়কে শীর্ষ ধরে দীর্ঘতম পথ। সব মোড়ের এমন সেরা-জোড়ার মধ্যে সবচেয়ে বড়টাই পুরো জালের ব্যাস। উপরের মোড়ে গেলে অবশ্য একটাই দিক বয়ে নিয়ে যেতে পারবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Diameter of Binary Tree** (#18)-এর সরাসরি সাধারণীকরণ। সেখানে প্রতিটা node-এ দুই child-এর height যোগ করে diameter পেতে; এখানে child দুটো নয় — যত খুশি — তাই প্রতিটা node-এ সব child-এর height-এর মধ্যে **সবচেয়ে বড় দুটো** নিয়ে যোগ করতে হয়। মূল চাল একই: "প্রতিটা node-কে path-এর চূড়া ধরে দুই সেরা arm যোগ করো, পাশে global max রাখো।"
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic — height return করি, পাশে diameter track করি:
```text
height(u) = 1 + max(height(c)) over children c (edge-গোনায় leaf height 0)
প্রতিটা node u-তে: সব child-এর (height(c)+1) থেকে সেরা দুটো top1, top2 নাও
diameter = max(diameter, top1 + top2) # u-কে চূড়া ধরে দুই arm
return top1 # উপরে শুধু এক arm যায়
```
মূল বুদ্ধি: u দিয়ে যাওয়া সবচেয়ে লম্বা path = তার দুই গভীরতম child-শাখা জোড়া দেওয়া; কিন্তু parent-এর কাছে u শুধু **একটা** (গভীরতম) শাখা দিতে পারে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **adjacency list** (`adj[u]` = u-র প্রতিবেশীদের list), একটা **side variable** `diameter`, আর **DFS**। যেহেতু tree unrooted ও general, প্রতিটা DFS-এ parent মনে রাখতে হয় (যাতে যেদিক থেকে এলাম সেদিকে ফিরে না যাই)। CSES-এ `n` বিশাল ও chain গভীর হতে পারে — তাই **iterative DFS** (বা recursion limit বাড়ানো) লাগে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
General unrooted tree-তে edge দু'মুখী, child-সংখ্যা যেকোনো — **adjacency list** নমনীয়ভাবে সব প্রতিবেশী ধরে, আর parent বাদ দিলে সেটাই কার্যত rooted DFS হয়ে যায়। diameter যেকোনো node-এ চূড়া পেতে পারে, তাই একটা **side variable** সব node-এর "দুই-arm যোগফল"-এর সর্বোচ্চটা ধরে। বিশাল `n`-এ Python recursion ভেঙে পড়ে, তাই **explicit stack** নিরাপদ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা node থেকে আলাদা BFS/DFS চালিয়ে বাকি সব node-এর দূরত্ব মাপো, সবচেয়ে দূরেরটা রাখো, তারপর সব node-এর সর্বোচ্চটা নাও।
```text
1) প্রতিটা node u-র জন্য:
2) u থেকে BFS করে সব দূরত্ব বের করো
3) সবচেয়ে দূরের দূরত্ব মনে রাখো (eccentricity)
4) সব eccentricity-র max = diameter
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা node থেকে একটা পূর্ণ traversal মানে **O(n²)** — n = ২ লক্ষ হলে অসম্ভব। দুটো ভালো বিকল্প আছে, দুটোই O(n): (১) **single-DFS** — প্রতিটা node-এ সেরা দুই child-height যোগ করে diameter পাও (Diameter #18-এর সাধারণীকরণ); (২) **two-BFS চাল** — যেকোনো node থেকে সবচেয়ে দূরের node `a` খোঁজো, তারপর `a` থেকে সবচেয়ে দূরের `b`; `a`–`b` দূরত্বই diameter। এখানে আমরা single-DFS করব।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **যেকোনো node-কে path-এর চূড়া ধরলে, সেখানে দীর্ঘতম path = তার দুই গভীরতম child-শাখার যোগফল।** তাই প্রতিটা node-এ সব child-arm থেকে **সেরা দুটো** নিয়ে যোগ করলেই সেই node-এ সম্ভাব্য diameter পাওয়া যায়; সব node-এর এমন মানের সর্বোচ্চটাই উত্তর। parent-কে অবশ্য শুধু **একটা** (গভীরতম) arm দেওয়া যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা DFS চালাও যেটা প্রতিটা node থেকে **নিচে নামা সর্বোচ্চ height** (edge-এ) ফেরত দেয়। প্রতিটা node-এ সব child-এর `height(c)+1` সংগ্রহ করো; তার মধ্যে top1 ও top2 (না থাকলে 0) দিয়ে `diameter = max(diameter, top1 + top2)` update করো; return করো `top1`। বিশাল/গভীর tree-তে recursion limit ভাঙতে পারে, তাই একটা explicit-stack iterative postorder ব্যবহার করো। পুরো tree একবার ঘোরা → O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** binary diameter থেকে এখানে আসতে শুধু "left আর right" বদলে "সব child-এর মধ্যে সেরা দুই" ভাবো — বাকি কাঠামো (return এক arm, update দুই arm) হুবহু একই। আর CP-মোচড়: `n` বিশাল হলে naive recursion stack overflow করবে — তাই হয় iterative DFS লেখো, নয়তো `sys.setrecursionlimit` বাড়িয়ে নাও। (চাইলে two-BFS চালও আছে, কিন্তু single-DFS-ই #18-এর সরাসরি জ্ঞাতি।)
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা node-এ সেরা দুই arm যোগ করে diameter; height উপরে এক arm যায়:
```text
1 arm থেকে: top1=2 (1-3-4), top2=1 (1-2) → 2+1 = 3 ← diameter
/ \
2 3 3-এ: top1=1 (3-4), top2=1 (3-5) → 1+1 = 2
/ \
4 5 leaf height 0
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n = 5`, edges `(1,2),(1,3),(3,4),(3,5)`, root ধরি 1, `diameter = 0`:
1. height(2): leaf (parent 1 বাদে কেউ নেই) → return 0।
2. height(4): leaf → 0; height(5): leaf → 0।
3. height(3): child 4,5-এর arm = 0+1, 0+1 → top1=1, top2=1 → `diameter = max(0, 1+1) = 2`; return 1।
4. height(1): child 2,3-এর arm = (0+1)=1, (1+1)=2 → top1=2, top2=1 → `diameter = max(2, 2+1) = 3`; return 2।
5. উত্তর = `diameter` = **3** (path 2→1→3→4)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import sys
from collections import deque
def tree_diameter(n, edges):
"""n-node general tree-র diameter (edge সংখ্যায়); edges দু'মুখী।"""
adj = [[] for _ in range(n + 1)] # 1-indexed adjacency list
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
if n == 1: # একা node, কোনো edge নেই
return 0
# iterative DFS: প্রথমে parent সহ একটা visit-order বানাই
root = 1
parent = [0] * (n + 1)
order, stack = [], [root]
parent[root] = -1 # root-এর parent নেই
while stack:
u = stack.pop()
order.append(u)
for w in adj[u]:
if w != parent[u]:
parent[w] = u
stack.append(w)
height = [0] * (n + 1) # node থেকে নিচে নামা সর্বোচ্চ edge-দূরত্ব
diameter = 0
for u in reversed(order): # পাতা → root ক্রমে (postorder)
top1 = top2 = 0 # সেরা দুই child-arm
for w in adj[u]:
if w == parent[u]:
continue
arm = height[w] + 1
if arm > top1:
top1, top2 = arm, top1
elif arm > top2:
top2 = arm
diameter = max(diameter, top1 + top2) # u-কে চূড়া ধরে দুই arm
height[u] = top1 # উপরে শুধু এক arm
return diameter
# ---- tests ----
assert tree_diameter(5, [(1, 2), (1, 3), (3, 4), (3, 5)]) == 3
assert tree_diameter(1, []) == 0 # একা node
assert tree_diameter(2, [(1, 2)]) == 1 # একটামাত্র edge
assert tree_diameter(4, [(1, 2), (2, 3), (3, 4)]) == 3 # সোজা chain
# তারা-আকার: কেন্দ্র 1-এর সাথে 2,3,4,5 — দীর্ঘতম path যেকোনো দুই পাতা = 2 edge
assert tree_diameter(5, [(1, 2), (1, 3), (1, 4), (1, 5)]) == 2
# গভীর chain (iterative হওয়ায় overflow হয় না): 1-2-...-2000 → diameter 1999
deep_edges = [(i, i + 1) for i in range(1, 2000)]
assert tree_diameter(2000, deep_edges) == 1999
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `adj = [[] for _ in range(n + 1)]; ... adj[u].append(v); adj[v].append(u)` — 1-indexed, দু'মুখী adjacency list (edge উভয় দিকে)।
- `if n == 1: return 0` — একা node-এ কোনো edge নেই, diameter 0।
- iterative DFS (`order`, `parent`) — recursion ছাড়া একটা visit-order ও প্রতিটা node-এর parent বের করি; `w != parent[u]` যেদিক থেকে এলাম সেদিকে ফেরা আটকায়।
- `for u in reversed(order):` — order উল্টালে প্রতিটা parent-এর আগে তার সব child আসে → বৈধ postorder।
- `top1, top2` লুপ — u-র সব child-arm (`height[w]+1`)-এর মধ্যে সেরা দুটো রাখি (general tree বলে দুইয়ের বেশি child হতে পারে)।
- `diameter = max(diameter, top1 + top2)` — u-কে চূড়া ধরে দুই গভীরতম arm যোগ; global update।
- `height[u] = top1` — parent-কে শুধু গভীরতম এক arm ফেরত দিই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`tree_diameter(5, [(1,2),(1,3),(3,4),(3,5)])` দেয় 3 (path 2→1→3→4) — assert pass। একা node দেয় 0, একটা edge দেয় 1, 4-node chain দেয় 3, তারা-আকার দেয় 2 (যেকোনো দুই পাতা)। 2000-node গভীর chain-এও iterative হওয়ায় overflow ছাড়া 1999 দেয় — pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — order বানাতে প্রতিটা node ও edge একবার, height/diameter জমাতে প্রতিটা node ও তার edge আরেকবার; tree-তে edge n−1টা, তাই মোট রৈখিক। n = ২ লক্ষেও দ্রুত।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — adjacency list O(n) (দু'মুখী edge), `parent`/`height`/`order`/`stack` প্রতিটা O(n)। iterative DFS হওয়ায় recursion call stack-এর O(n) গভীরতা এড়ানো গেছে — naive recursion-এ ওটাই গভীর chain-এ overflow ঘটাত।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- recursive DFS দিয়ে ২ লক্ষ-লম্বা chain-এ **RecursionError** — iterative DFS বা বাড়ানো recursion limit লাগে।
- parent বাদ না দেওয়া — তখন DFS যেদিক থেকে এসেছে সেদিকে ফিরে গিয়ে infinite loop/ভুল height হয় (unrooted tree বলে edge দু'মুখী)।
- শুধু top1 দিয়ে diameter হিসাব করা — চূড়ায় **দুই** arm লাগে; top2 ভুললে diameter কম আসে।
- edge-গোনা বনাম node-গোনা গুলিয়ে ফেলা — এই problem **edge** গোনে, তাই leaf height 0, একটা edge-এ diameter 1।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Diameter of Binary Tree (#18)-এর "height return, পাশে দুই-arm diameter track" আর Subordinates (#22)-এর general-tree iterative DFS। দুটো এক হলে — সেরা-দুই-arm + বড় ইনপুটে iterative — CSES Tree Diameter দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Diameter of Binary Tree (একই ধারণা, binary সংস্করণ) —