Xét ~P~ là một tập con các cạnh trong cây, sao cho mỗi đỉnh đều được phủ bởi nhiều nhất hai cạnh trong tập ~P~. Khi đó, ứng với một tập ~P~ bất kì, ta đều có một lộ trình du lịch với chi phí ~A \cdot \sum{i \in P \ w_i} + B \cdot (cnt(P) + 1)~ với ~cnt(P)~ là số cạnh không thuộc tập ~P~.

Từ đây, ta sẽ có được thuật toán quy hoạch động:

~dp[u][i]~: xét trong cây con gốc ~u~, chi phí nhỏ nhất để chọn tập ~P~ có tối đa ~i~ cạnh đang phủ ~u~.

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

#define f first
#define s second
#define _size(x) (int)x.size()

const int maxn = 2e5 + 5;
const long long inf = 1e18;

int n;
long long a, b;
vector<vector<pair<int, long long>>> adj(maxn);

namespace full {

    int vis[maxn];
    long long f[maxn][3];

    void dfs(int u) {

        f[u][0] = 0;
        f[u][1] = f[u][2] = inf;
        vis[u]++;
        for (auto e: adj[u]) {
            int v = e.f;
            long long c = e.s;
            if (vis[v]) continue;
            dfs(v);
            f[u][2] = min(f[u][1] + min({f[v][0], f[v][1]}) + min(c * a, b), f[u][2] + min({f[v][0], f[v][1], f[v][2]}) + b);
            f[u][1] = min(f[u][0] + min({f[v][0], f[v][1]}) + min(c * a, b), f[u][1] + min({f[v][0], f[v][1], f[v][2]}) + b);
            f[u][0] += min({f[v][0], f[v][1], f[v][2]}) + b;
        }
    }

    void main() {

        dfs(1);
        cout << min({f[1][0], f[1][1], f[1][2]}) + b << '\n';
    }
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    full::main();
    return 0;
}