2646. Minimize the Total Price of the Trips

There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

Each node has an associated price. You are given an integer array price, where price[i] is the price of the ith node.

The price sum of a given path is the sum of the prices of all nodes lying on that path.

Additionally, you are given a 2D integer array trips, where trips[i] = [starti, endi] indicates that you start the ith trip from the node starti and travel to the node endi by any path you like.

Before performing your first trip, you can choose some non-adjacent nodes and halve the prices.

Return the minimum total price sum to perform all the given trips.

class Solution {
    vector<int> adj[55];
    vector<int> p;
    vector<int> freq;
    void dfs(int u, int par, int goal, vector<int>& path) {
        path.push_back(u);
        if(u == goal) return;
        for(auto& v : adj[u]) {
            if(v == par) continue;
            dfs(v,u,goal,path);
            if(path.back() == goal) return;
        }
        path.pop_back();
    }
    void mark(int u, int v) {
        vector<int> path;
        dfs(u,-1,v,path);
        for(auto p : path) freq[p] += 1;
    }
    pair<long long, long long> helper(int u, int par) {
        long long self = 0, child = 0;
        for(auto& v : adj[u]) {
            if(v == par) continue;
            auto [cs, cc] = helper(v,u);
            self += cc, child += cs;
        }
        self += p[u] / 2 * freq[u];
        self = max(self, child);
        return {self, child};
    }
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        freq = vector<int>(n);
        p = price;
        for(int i = 0; i < n; i++) adj[i].clear();
        for(auto e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        for(auto t : trips) mark(t[0],t[1]);
        auto [a,b] = helper(0,-1);
        long long res = 0;
        for(int i = 0; i < n; i++) {
            res += freq[i] * p[i];
        }
        res -= max(a,b);
        return res;
    }
};