ผลรวมของระยะทางในต้นไม้ใน C++

สมมติว่าเรามีต้นไม้ที่เชื่อมต่อแบบไม่มีทิศทางและมีโหนด N อยู่ สิ่งเหล่านี้ถูกระบุว่าเป็น 0...N-1 และขอบ N-1 ขอบ ith เชื่อมต่อโหนด edge[i][0] และ edge[i][1] เข้าด้วยกัน เราต้องหารายการที่ ans[i] คือผลรวมของระยะทางระหว่างโหนด i และโหนดอื่นๆ ทั้งหมด

ดังนั้น หากอินพุตเป็น N =6 และ edge =[(0,1),(0,2),(2,3),(2,4),(2,5)] ผลลัพธ์จะเป็น [8,12,6,10,10,10]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs1() ซึ่งจะใช้โหนด พาเรนต์

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[โหนด] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ลูก :=กราฟ[โหนด ผม]

    • ถ้าลูกไม่เท่ากับพ่อแม่ −

      • dfs1(ลูก, โหนด)

      • cnt[node] :=cnt[node] + cnt[ลูก]

      • ans[node] :=ans[node] + cnt[child] + ans[child]

• กำหนดฟังก์ชัน dfs2() ซึ่งจะใช้โหนด พาเรนต์

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[โหนด] อัปเดต (เพิ่ม i โดย 1) ทำ−

    • ลูก :=กราฟ[โหนด ผม]

    • ถ้าลูกไม่เท่ากับพ่อแม่ −

      • ans[child] :=ans[node] - cnt[child] + N - cnt[child]

      • dfs2(ลูก โหนด

• กำหนดอาร์เรย์และ

• กำหนดอาร์เรย์ cnt

• กำหนดกราฟอาร์เรย์ด้วย 1,0005 แถว

• จากวิธีหลัก ให้ทำดังนี้ −

• ไม่มีสิ่งนี้ :=N

• ans :=กำหนดอาร์เรย์ขนาด N

• cnt :=กำหนดอาร์เรย์ขนาด N เติมด้วย 1

• n :=ขนาดของขอบ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • u :=edge[i, 0]

  • v :=ขอบ[i, 1]

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้ายกราฟ[v]

• dfs1(0, -1)

• dfs2(0, -1)

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;void print_vector(vector v){ cout <<"["; for(int i =0; i ans; เวกเตอร์ cnt; เวกเตอร์ กราฟ[10005]; อินท์ N; vector sumOfDistancesInTree(int N, vector>&ขอบ) { this->N =N; ans =vector(N); cnt =เวกเตอร์(N, 1); int n =edge.size(); สำหรับ (int i =0; i > v ={{0,1},{0,2},{2,3},{2,4},{2,5}}; print_vector(ob.sumOfDistancesInTree(6, v));}

อินพุต

ผลลัพธ์

[8, 12, 6, 10, 10, 10, ]