Daily DSA: Maximum Weighted K-Edge Component (Hard)
Problem Statement
You are given an undirected tree with $N$ vertices, rooted at vertex 1. Each vertex $u$ has a positive weight $W[u]$. Your task is to select a connected subgraph (a connected component) containing exactly $K$ edges such that the sum of weights of the vertices in this subgraph is maximized.
Since the subgraph is connected and has $K$ edges, it must contain exactly $K + 1$ vertices. If no such connected component exists, return -1.
Examples
Example 1:
Input:
N = 5, K = 2
Edges = [[1, 2], [1, 3], [2, 4], [2, 5]]
Weights = [10, 20, 5, 1, 2]
Output:
32
Explanation:
We need a connected component with 2 edges (3 vertices). If we pick vertices {1, 2, 4} with edges [1, 2] and [2, 4], the sum of weights is $10 + 20 + 5 = 35$. Wait, letโs check another: {1, 2, 5} with edges [1, 2] and [2, 5] gives $10 + 20 + 2 = 32$. Letโs maximize carefully. With $K=2$, selecting root 1, child 2, and grandchild 4 forms a path/subtree of 2 edges: $1-2$ and $2-4$, total weight $10 + 20 + 5 = 35$.
Example 2:
Input:
N = 4, K = 3
Edges = [[1, 2], [2, 3], [3, 4]]
Weights = [5, 5, 5, 5]
Output:
20
Explanation:
The tree is a line graph $1-2-3-4$. Selecting all 4 vertices involves 3 edges, and the sum of weights is $5 + 5 + 5 + 5 = 20$.
Constraints
- $1 \le N \le 300$
- $0 \le K \le N - 1$
- $1 \le W[u] \le 1000$
Approach
- Tree DP with Knapsack (Merging Subtrees): This is a classic tree knapsack problem. For each node $u$, we want to compute the maximum weight of a connected component containing $u$ and restricted to the subtree rooted at $u$, using exactly $j$ edges ($0 \le j \le \text{size of subtree of } u$).
- State Definition: Let
dp[u][j]be the maximum weight of a connected component containing $u$ in the subtree of $u$ that uses exactly $j$ edges. - Transition:
- Initialize
dp[u][0] = W[u](since the component must contain $u$, using 0 edges means just the node $u$ itself, though if $K > 0$, this will be combined later). - When processing a child $v$ of $u$, we can either:
- Include the edge $(u, v)$ and some number of edges $j_v$ from subtree $v$.
- Or not include the edge to $v$ (which means we take nothing from subtree $v$).
- This is modeled via a knapsack-like combination where we merge the DP array of $u$ with the DP array of $v$. Specifically, if we use $j_u$ edges in the current component of $u$ and $j_v$ edges in subtree $v$, using edge $(u,v)$ takes $1 + j_v$ edges from the branch of $v$.
- Initialize
- Complexity: Since merging two subtrees of sizes $S_1$ and $S_2$ takes $O(S_1 \times S_2)$ time, doing this for all nodes in a tree results in an overall time complexity of $O(N^2)$.
C++ Solution
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
private:
int n, targetK;
vector<vector<int>> adj;
vector<int> weight;
// dp[u][j] = max weight of connected component containing u in subtree of u with j edges
vector<vector<int>> dp;
vector<int> sz;
void dfs(int u, int p) {
dp[u][0] = weight[u];
sz[u] = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
// Temporary array to store merged results for u
vector<int> next_dp(sz[u] + sz[v] + 2, -1);
for (int i = 0; i <= sz[u]; ++i) {
if (dp[u][i] == -1) continue;
for (int j = 0; j <= sz[v] + 1; ++j) {
if (dp[v][j - 1] == -1 && j > 0) continue;
// Option 1: Do not use edge (u, v)
// (Handled by keeping dp[u][i])
// Option 2: Use edge (u, v) and j edges from subtree v (where j >= 1)
if (j > 0 && dp[v][j - 1] != -1) {
if (dp[u][i] != -1) {
next_dp[i + j] = max(next_dp[i + j], dp[u][i] + dp[v][j - 1]);
}
}
}
}
// Also we can just carry over existing dp[u][i] without using v
for (int i = 0; i <= sz[u]; ++i) {
if (dp[u][i] != -1) {
next_dp[i] = max(next_dp[i], dp[u][i]);
}
}
sz[u] += sz[v] + 1;
dp[u] = move(next_dp);
}
}
public:
int maxWeightedComponent(int N, int K, vector<vector<int>>& edges, vector<int>& W) {
n = N;
targetK = K;
weight = W;
adj.assign(n + 1, vector<int>());
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
dp.assign(n + 1, vector<int>(n, -1));
sz.assign(n + 1, 0);
dfs(1, 0);
int ans = -1;
for (int i = 1; i <= n; ++i) {
if (targetK < dp[i].size() && dp[i][targetK] != -1) {
ans = max(ans, dp[i][targetK]);
}
}
return ans;
}
};
Complexity Analysis
- Time Complexity: $O(N^2)$, where $N$ is the number of vertices. The tree knapsack merge takes proportional to the product of subtree sizes, which totals $O(N^2)$ across all tree merges.
- Space Complexity: $O(N^2)$ to store the DP table across all nodes, plus $O(N)$ recursion stack space.