AC - Select Edges

Explanation

To solve this problem, we write a tree DP. Consider that the only factor we need to differentiate nodes on is whether or not we can connect a given node to its parent. Thus, our DP state is the following:

• $\texttt{dp}[u][0]$ is the best result in the subtree of $u$ if we can connect $u$ to its parent
• $\texttt{dp}[u][1]$ is the best result in the subtree of $u$ if we can't connect $u$ to its parent

For a given node $u$, the "gain" we get from adding this node in is:

Thus, we want to use our $d[u]$ allowed edges on the nodes that have the most benefit when adding an edge to them. Note that we handle the cases for $\texttt{dp}[u][0])$ and $\texttt{dp}[u][1]$ pretty similarly.

Implementation

Time Complexity: $\mathcal{O}(N\log{N})$

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

using ll = long long;

int main() {
	int n;
	cin >> n;

	vector<int> d(n);