Chương trình C++ tìm tổng lớn nhất của đồ thị cây khi gán giá trị đỉnh

Mô tả bài toán

Cho cây n đỉnh, mảng vertexValues n số. Gán các số này vào đỉnh (mỗi số 1 lần). Trên mỗi cạnh ghi giá trị nhỏ hơn của 2 đầu. Tổng giá trị cạnh = điểm số. Tối đa hóa điểm số và in cả gán giá trị.

Ví dụ

n=6, edges={{1,2},{2,3},{2,4},{4,5},{3,6}}, values={1,2,3,4,5,6}. Đầu ra: 15 và gán 3 1 2 4 5 6.

Thuật toán (DFS + Sắp xếp giá trị)

1. Sắp xếp tăng dần.
2. DFS từ gốc (đỉnh 0/1). Gán giá trị lớn nhất cho lá, dần về gốc.
3. Cụ thể: duyệt DFS, gán với giảm từ về 0. Nếu cộng vào đáp án.
4. Đáp án = tổng giá trị lớn nhất (trừ giá trị nhỏ nhất ở gốc).

Đoạn mã C++

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

const int N=100;
int seq[N], res[N];
vector<int> tp[N];
int ans=0, c;

void dfs(int u,int p){
    res[u]=seq[c];
    if(u!=0) ans+=seq[c];
    c--;
    for(int v:tp[u]) if(v!=p) dfs(v,u);
}

void solve(int n,vector<pair<int,int>> edges,int values[]){
    for(auto [a,b]:edges){
        a--; b--;
        tp[a].push_back(b);
        tp[b].push_back(a);
    }
    for(int i=0;i=0;i--) cout << res[i] << ' ';
    cout << '\n';
}

int main(){
    int n=6;
    vector<pair<int,int>> edges={{1,2},{2,3},{2,4},{4,5},{3,6}};
    int values[]={1,2,3,4,5,6};
    solve(n,edges,values);
    return 0;
}

Đầu vào / Đầu ra

Input: 6, {{1,2},{2,3},{2,4},{4,5},{3,6}}, {1,2,3,4,5,6}

Output: 15 3 1 2 4 5 6