Weighted Path Distribution via Greedy DFS
When distributing a fixed number of routes across a rooted tree, an optimal strategy balances load evenly before allocating surplus paths based on subtree potential. The algorithm performs a depth-first traversal where each node divides incoming routes equally among its children. The remainder is assigned to children with the highest subtree values, maximizing the global sum. A priority queue efficiently selects the top beneficiaries for the leftover routes.
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 100005;
vector<int> tree[MAXN];
long long nodeValue[MAXN], globalAccumulator = 0;
long long propagatePaths(int current, int incomingRoutes) {
globalAccumulator += incomingRoutes * nodeValue[current];
if (tree[current].empty()) return nodeValue[current];
int baseShare = incomingRoutes / tree[current].size();
int remainder = incomingRoutes % tree[current].size();
priority_queue<long long> maxHeap;
for (int child : tree[current]) {
maxHeap.push(propagatePaths(child, baseShare));
}
while (remainder-- > 0 && !maxHeap.empty()) {
globalAccumulator += maxHeap.top();
maxHeap.pop();
}
long long topChildVal = maxHeap.empty() ? 0 : maxHeap.top();
return topChildVal + nodeValue[current];
}
void execute() {
int n, m;
cin >> n >> m;
for (int i = 2; i <= n; ++i) {
int parent; cin >> parent;
tree[parent].push_back(i);
}
for (int i = 1; i <= n; ++i) cin >> nodeValue[i];
propagatePaths(1, m);
cout << globalAccumulator << '\n';
for (int i = 1; i <= n; ++i) tree[i].clear();
globalAccumulator = 0;
}
Maximizing Path Union with Diameter Analysis
To maximize the combined length of three non-overlapping paths in a tree, two endpoints must align with the tree's diameter. The third path originates from the node farthest away from this diameter. The approach identifies the diameter through two breadth-first traversals, marks all nodes on the diameter, and executes a multi-source BFS from these marked nodes to locate the optimal third vertex. Edge cases where the diameter spans the entire tree are handled by selecting an internal diameter node.
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 200005;
vector<int> adj[MAXN];
int depthFromStart[MAXN], distToDiameter[MAXN];
bool onDiameter[MAXN];
int farthestNode = 0;
void bfsCompute(int source, int n, int* distArr) {
fill(distArr, distArr + n + 1, -1);
queue<int> q;
q.push(source); distArr[source] = 0;
farthestNode = source;
while (!q.empty()) {
int u = q.front(); q.pop();
if (distArr[u] > distArr[farthestNode]) farthestNode = u;
for (int v : adj[u]) {
if (distArr[v] == -1) {
distArr[v] = distArr[u] + 1;
q.push(v);
}
}
}
}
void markDiameterPath(int u, int target, int parent) {
if (u == target) { onDiameter[u] = true; return; }
for (int v : adj[u]) {
if (v != parent) {
markDiameterPath(v, target, u);
if (onDiameter[v]) onDiameter[u] = true;
}
}
}
int main() {
ios::sync_with_stdio(false);
int n; cin >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
bfsCompute(1, n, depthFromStart);
int diaEndA = farthestNode;
bfsCompute(diaEndA, n, depthFromStart);
int diaEndB = farthestNode;
markDiameterPath(diaEndA, diaEndB, -1);
fill(distToDiameter, distToDiameter + n + 1, -1);
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (onDiameter[i]) {
distToDiameter[i] = 0; q.push(i);
}
}
int bestThird = 0, maxDist = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (distToDiameter[u] > maxDist) {
maxDist = distToDiameter[u]; bestThird = u;
}
for (int v : adj[u]) {
if (distToDiameter[v] == -1) {
distToDiameter[v] = distToDiameter[u] + 1;
q.push(v);
}
}
}
if (bestThird == 0) {
for (int i = 1; i <= n; ++i)
if (onDiameter[i] && i != diaEndA && i != diaEndB) { bestThird = i; break; }
}
cout << maxDist + depthFromStart[diaEndB] - 1 << '\n';
cout << diaEndA << ' ' << diaEndB << ' ' << bestThird << '\n';
return 0;
}
Constrained Tree Partisioning with State DP
This problem maps to a classic tree dynamic programming scenario where each vertex maintains two states: selected or excluded. The solution aggregates results bottom-up, ensuring that selection constraints are respected across parent-child relationships. The recurrence merges child states to maximize the accumulated weight while adhering to parity or adjacency rules.
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100005;
const long long NEG_INF = -1e18;
vector<int> children[MAXN];
long long val[MAXN], dp[MAXN][2];
void computeStates(int u) {
dp[u][1] = NEG_INF;
dp[u][0] = 0;
long long excludeSum = 0, includeSum = 0;
for (int v : children[u]) {
computeStates(v);
long long tempEx = dp[u][0], tempIn = dp[u][1];
dp[u][0] = max(tempEx + dp[v][0], tempEx + dp[v][1]);
dp[u][1] = max(tempIn + dp[v][0], tempIn + dp[v][1]);
}
dp[u][1] = max(dp[u][1], dp[u][0] + val[u]);
}
int main() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) {
int parent, w; cin >> parent >> w;
val[i] = w;
if (parent != -1) children[parent].push_back(i);
}
computeStates(1);
cout << max(dp[1][0], dp[1][1]) << '\n';
return 0;
}
Edge Selection Optimization Using Priority-Based DP
For trees where each node can connect to at most k children, a hybrid DP and greedy strategy proves effective. The base case assumes no edges are selected. By calculating the marginal gain of including an edge, these differences are sorted. The top k gains update the state allowing parent connections, while the top k-1 govern the restricted state, efficiently balancing local choices.
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;
const int MAXN = 200005;
struct Edge { int to, weight; };
vector<Edge> adj[MAXN];
long long dp[MAXN][2];
int limitK;
void traverse(int u, int parent) {
long long baseSum = 0;
vector<long long> gains;
for (auto &edge : adj[u]) {
if (edge.to == parent) continue;
traverse(edge.to, u);
baseSum += dp[edge.to][0];
gains.push_back(dp[edge.to][1] + edge.weight - dp[edge.to][0]);
}
sort(gains.begin(), gains.end(), greater<long long>());
dp[u][0] = baseSum;
dp[u][1] = baseSum;
for (int i = 0; i < (int)gains.size() && i < limitK; ++i) {
if (gains[i] <= 0) break;
if (i < limitK - 1) dp[u][1] += gains[i];
dp[u][0] += gains[i];
}
}
void processQuery() {
int n; cin >> n >> limitK;
for (int i = 1; i < n; ++i) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
traverse(1, 0);
cout << dp[1][0] << '\n';
for (int i = 1; i <= n; ++i) { adj[i].clear(); dp[i][0] = dp[i][1] = 0; }
}
int main() {
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) processQuery();
return 0;
}
Path-Weight Queries via Heavy-Light Decomposition
When evaluating the minimum spanning tree cost for every edge ensertion, the solution first constructs a baseline MST. For non-tree edges, forcing inclusion creates a cycle. Removing the heaviest edge on the fundamental cycle yields the new optimal weight. Heavy-Light Decomposition paired with a segment tree efficiently retrieves the maximum edge weight along any tree path, reducing query complexity from linear to logarithmic.
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;
const int MAXN = 100005;
struct QueryEdge { int u, v, w, id; };
vector<pair<int, int>> tree[MAXN];
int parentArr[MAXN], heavy[MAXN], depth[MAXN], head[MAXN], pos[MAXN], edgeVal[MAXN];
int segTree[MAXN << 2], subSize[MAXN], timer = 0;
int dsu[MAXN];
bool inMST[MAXN];
vector<QueryEdge> edges;
int n, m;
int findSet(int i) { return dsu[i] == i ? i : dsu[i] = findSet(dsu[i]); }
void unite(int i, int j) {
i = findSet(i); j = findSet(j);
if (i != j) dsu[i] = j;
}
void buildHLD(int u, int p, int d) {
depth[u] = d; parentArr[u] = p; subSize[u] = 1; heavy[u] = 0;
int maxSub = 0;
for (auto &[v, w] : tree[u]) {
if (v == p) continue;
edgeVal[v] = w;
buildHLD(v, u, d + 1);
subSize[u] += subSize[v];
if (subSize[v] > maxSub) { maxSub = subSize[v]; heavy[u] = v; }
}
}
void decompose(int u, int h) {
head[u] = h; pos[u] = ++timer;
if (heavy[u]) decompose(heavy[u], h);
for (auto &[v, w] : tree[u])
if (v != parentArr[u] && v != heavy[u]) decompose(v, v);
}
void updateSeg(int node, int l, int r, int idx, int val) {
if (l == r) { segTree[node] = val; return; }
int mid = (l + r) / 2;
idx <= mid ? updateSeg(node*2, l, mid, idx, val) : updateSeg(node*2+1, mid+1, r, idx, val);
segTree[node] = max(segTree[node*2], segTree[node*2+1]);
}
int querySeg(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return segTree[node];
int mid = (l + r) / 2;
return max(querySeg(node*2, l, mid, ql, qr), querySeg(node*2+1, mid+1, r, ql, qr));
}
int queryPathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
res = max(res, querySeg(1, 1, n, pos[head[u]], pos[u]));
u = parentArr[head[u]];
}
if (depth[u] > depth[v]) swap(u, v);
if (u != v) res = max(res, querySeg(1, 1, n, pos[u] + 1, pos[v]));
return res;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
edges.resize(m + 1);
for (int i = 1; i <= n; ++i) dsu[i] = i;
for (int i = 1; i <= m; ++i) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
edges[i].id = i;
}
sort(edges.begin() + 1, edges.end(), [](const QueryEdge &a, const QueryEdge &b) { return a.w < b.w; });
long long mstWeight = 0;
for (int i = 1; i <= m; ++i) {
if (findSet(edges[i].u) != findSet(edges[i].v)) {
unite(edges[i].u, edges[i].v);
tree[edges[i].u].push_back({edges[i].v, edges[i].w});
tree[edges[i].v].push_back({edges[i].u, edges[i].w});
mstWeight += edges[i].w;
inMST[edges[i].id] = true;
}
}
buildHLD(1, 0, 0);
decompose(1, 1);
for (int i = 2; i <= n; ++i) updateSeg(1, 1, n, pos[i], edgeVal[i]);
for (int i = 1; i <= m; ++i) {
if (inMST[edges[i].id]) cout << mstWeight << '\n';
else cout << mstWeight + edges[i].w - queryPathMax(edges[i].u, edges[i].v) << '\n';
}
return 0;
}
Linearized Coloring with Sequential Constraints
Despite appearing as a tree, structures with maximum degree two reduce to simple paths. This allows a shift from recursive tree DP to iterative linear dynamic programming. By enforcing color constraints across adjacent and distance-two vertices, the algorithm tracks the last two assigned colors. The state transitions iterate over valid color triplets, accumulating minimal costs and maintaining backtracking pointers for solution reconstruction.
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;
const int INF = 1e9;
int cost[3][MAXN], adj[MAXN], path[MAXN], deg[MAXN];
int dp[MAXN][3][3], backtrack[MAXN][3][3];
int assignment[MAXN];
int n;
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int c = 0; c < 3; ++c)
for (int i = 1; i <= n; ++i) cin >> cost[c][i];
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
adj[u] = v; adj[v] = u;
deg[u]++; deg[v]++;
}
for (int i = 1; i <= n; ++i) {
if (deg[i] > 2) { cout << -1 << '\n'; return 0; }
}
int start = 1;
for (int i = 1; i <= n; ++i) if (deg[i] == 1) { start = i; break; }
int u = start, p = 0;
for (int i = 0; i < n; ++i) {
path[i] = u;
int next = adj[u];
adj[u] = p;
p = u; u = next;
}
for (int i = 0; i < n; ++i)
for (int c1 = 0; c1 < 3; ++c1)
for (int c2 = 0; c2 < 3; ++c2)
dp[i][c1][c2] = INF;
for (int c1 = 0; c1 < 3; ++c1)
for (int c2 = 0; c2 < 3; ++c2)
if (c1 != c2)
dp[1][c1][c2] = cost[c1][path[0]] + cost[c2][path[1]];
for (int i = 2; i < n; ++i) {
for (int c1 = 0; c1 < 3; ++c1) {
for (int c2 = 0; c2 < 3; ++c2) {
if (dp[i-1][c1][c2] == INF) continue;
for (int c3 = 0; c3 < 3; ++c3) {
if (c3 == c2 || c3 == c1) continue;
int newVal = dp[i-1][c1][c2] + cost[c3][path[i]];
if (newVal < dp[i][c2][c3]) {
dp[i][c2][c3] = newVal;
backtrack[i][c2][c3] = c1;
}
}
}
}
}
int minTotal = INF, last1 = 0, last2 = 0;
for (int c1 = 0; c1 < 3; ++c1)
for (int c2 = 0; c2 < 3; ++c2)
if (dp[n-1][c1][c2] < minTotal) {
minTotal = dp[n-1][c1][c2]; last1 = c1; last2 = c2;
}
assignment[path[n-1]] = last1 + 1;
assignment[path[n-2]] = last2 + 1;
for (int i = n - 1; i >= 2; --i) {
int prev = backtrack[i][last1][last2];
assignment[path[i-3]] = prev + 1;
last2 = last1; last1 = prev;
}
cout << minTotal << '\n';
for (int i = 1; i <= n; ++i) cout << assignment[i] << ' ';
cout << '\n';
return 0;
}