เวลาน้อยที่สุดในการเก็บแอปเปิ้ลทั้งหมดในต้นไม้ใน C++

สมมติว่ามี undirected tree n โหนด 0 ถึง n-1 บางโหนดมีแอปเปิ้ล ใช้เวลา 1 วินาทีต่อ edge เราต้องหาเวลาน้อยที่สุดในการเก็บแอปเปิ้ลทั้งหมดเริ่มจากโหนด 0 และกลับมาที่ 0

ตัวอย่าง: n=7, edges=[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple=[f,f,t,f,t,t,f] ผลลัพธ์ = 8

วิธีแก้ปัญหา (DFS)

1. สร้าง adjacency list จาก edges
2. DFS จาก root 0:
   • คืนค่า true ถ้า subtree นี้มีแอปเปิ้ล (รวมตัวเอง)
   • ถ้า child subtree มีแอปเปิ้ล เพิ่มเวลา 2 (ไป-กลับ)
3. ผลรวมเวลา = คำตอบ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

const int N = 1e6; 

class Solution { 
public: 
    set<int> visited; 
    int ret; 
    
    int dfs(int node, int par, vector<bool>& a, vector<int> graph[]){ 
        int temp = 0; 
        for (int x : graph[node]) { 
            if (x == par) continue; 
            temp += dfs(x, node, a, graph); 
        } 
        ret += temp * 2; 
        return a[node] + temp > 0; 
    } 
    
    int minTime(int n, vector<vector<int>>& e, vector<bool>& a){ 
        ret = 0; 
        vector<int> graph[n]; 
        for (int i = 0; i < e.size(); i++) { 
            graph[e[i][0]].push_back(e[i][1]); 
            graph[e[i][1]].push_back(e[i][0]); 
        } 
        dfs(0, -1, a, graph); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}}; 
    vector<bool> v1 = {false,false,true,false,true,true,false}; 
    cout << (ob.minTime(7,v, v1)); 
}

ข้อมูลนำเข้า

7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}}, {false,false,true,false,true,true,false}

ผลลัพธ์

8