Weighted Independent Set with Point Updates on a Tree

Consider a rooted tree where every node carries a weight. We must support point-weight modifications and after each change report the maximum-weight independent set of the entire tree. Node count and operation count are up to (10^5), weights are bounded in absolute value by (10^2).

Standard tree DP defines (f_{u,1}) (node (u) chosen) and (f_{u,0}) (node (u) not chosen). The recurrences are: [ f_{u,0}=\sum_{v}\max(f_{v,0},f_{v,1}) ] [ f_{u,1}=a_u+\sum_{v}f_{v,0} ] Here (v) iterates over all children of (u). A single weight change can propagate up to the root, giving (O(depth)) time per update, which degenerates to (O(n)) on a chain.

To accelerate updates we apply heavy-light decomposition (HLD). Define light-child contributions (g_{u,1}, g_{u,0}): they capture the same DP choices restricted to light subtrees. For a heavy child (v) of (u): [ f_{u,0}=g_{u,0}+\max(f_{v,0},f_{v,1}) ] [ f_{u,1}=g_{u,1}+f_{v,0} ] These equations combine linearly under a max-plus matrix multiplication. Define multiplication of matrices (A) and (B) as: [ C_{i,j}=\max_k (A_{i,k}+B_{k,j}) ] We represent the DP vector as a column (\begin{bmatrix}f_{u,0}\ f_{u,1}\end{bmatrix}). Transition from heavy child (v) to (u) is a left-multiplication by a matrix (M_u) built from (g_{u,*}): [ \begin{bmatrix}f_{u,0}\ f_{u,1}\end{bmatrix}

\begin{bmatrix}g_{u,0} & g_{u,0}\ g_{u,1} & -\infty\end{bmatrix} \begin{bmatrix}f_{v,0}\ f_{v,1}\end{bmatrix} ] A segment tree stores the product of such matrices over every heavy path. The path's bottom (leafmost node) has an easily initialized DP vector; multiplying matrices upward gives the DP values at the path's top.

Important implementation choices:

• For each node keep a matrix val[u] that encodes the light-child contributions.
• Precompute for every heavy-path the index range of the path and store its end (ed).
• Query the segment tree from a node down to the end of its heavy path to retrieve the current DP vector at that node.
• To apply a point update, adjust the weight, recompute the affected matrix, then walk upward along HLD chains: remove the old contribution of the changed subtree from the parent's light-matrix, insert the new contribution, and repeat until reaching the root.

Time complexity (O(n\log^2 n)) with a small constant factor from 2×2 max-plus matrix multiplication.

Example Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e9;
int n, m, a[N];
vector<int> g[N];
int parent[N], sz[N], depth[N], heavy[N], head[N], pos[N], rev[N], tail[N], timer;
int dp[N][2];

struct Matrix {
    int m[2][2];
    Matrix() { m[0][0]=m[0][1]=m[1][0]=m[1][1]=-INF; }
    Matrix operator*(const Matrix &b) const {
        Matrix c;
        for (int i=0;i<2;++i)
            for (int k=0;k<2;++k)
                for (int j=0;j<2;++j)
                    c.m[i][j]=max(c.m[i][j], m[i][k]+b.m[k][j]);
        return c;
    }
} val[N], seg[N<<2];

#define lc (p<<1)
#define rc (p<<1|1)
void pull(int p) { seg[p]=seg[lc]*seg[rc]; }
void build(int p, int l, int r) {
    if (l == r) { seg[p] = val[rev[l]]; return; }
    int mid = (l+r)>>1;
    build(lc,l,mid); build(rc,mid+1,r);
    pull(p);
}
void update(int p, int l, int r, int x) {
    if (l == r) { seg[p] = val[rev[l]]; return; }
    int mid = (l+r)>>1;
    if (x<=mid) update(lc,l,mid,x); else update(rc,mid+1,r,x);
    pull(p);
}
Matrix query(int p, int l, int r, int ql, int qr) {
    if (ql==l && qr==r) return seg[p];
    int mid = (l+r)>>1;
    if (qr<=mid) return query(lc,l,mid,ql,qr);
    if (ql>mid) return query(rc,mid+1,r,ql,qr);
    return query(lc,l,mid,ql,mid)*query(rc,mid+1,r,mid+1,qr);
}

void dfs1(int u, int p) {
    parent[u]=p; depth[u]=depth[p]+1; sz[u]=1;
    for (int v: g[u]) if (v!=p) {
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[heavy[u]]) heavy[u]=v;
    }
}
void dfs2(int u, int h) {
    head[u]=h; pos[u]=++timer; rev[timer]=u;
    tail[h]=max(tail[h], timer);
    dp[u][0]=0; dp[u][1]=a[u];
    val[u].m[0][0]=val[u].m[0][1]=0;
    val[u].m[1][0]=a[u];
    if (heavy[u]) {
        dfs2(heavy[u], h);
        dp[u][0]+=max(dp[heavy[u]][0], dp[heavy[u]][1]);
        dp[u][1]+=dp[heavy[u]][0];
    }
    for (int v: g[u]) if (v!=parent[u] && v!=heavy[u]) {
        dfs2(v, v);
        dp[u][0]+=max(dp[v][0], dp[v][1]);
        dp[u][1]+=dp[v][0];
        val[u].m[0][0]+=max(dp[v][0], dp[v][1]);
        val[u].m[0][1]=val[u].m[0][0];
        val[u].m[1][0]+=dp[v][0];
    }
}
void modify(int u, int w) {
    val[u].m[1][0] += w-a[u];
    a[u] = w;
    Matrix before, after;
    while (u) {
        before = query(1,1,n,pos[head[u]],tail[head[u]]);
        update(1,1,n,pos[u]);
        after  = query(1,1,n,pos[head[u]],tail[head[u]]);
        u = parent[head[u]];
        val[u].m[0][0] += max(after.m[0][0],after.m[1][0]) - max(before.m[0][0],before.m[1][0]);
        val[u].m[0][1] = val[u].m[0][0];
        val[u].m[1][0] += after.m[0][0] - before.m[0][0];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    for (int i=1,u,v;i<n;++i) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); }
    depth[1]=1; dfs1(1,0); dfs2(1,1);
    build(1,1,n);
    while (m--) {
        int u,w; scanf("%d%d",&u,&w);
        modify(u,w);
        Matrix ans = query(1,1,n,pos[1],tail[1]);
        printf("%d\n", max(ans.m[0][0], ans.m[1][0]));
    }
    return 0;
}

Minimum-Weight Vertex Cover with Forced Selections

Given a vertex-weighted tree and multiple queries specifying forced inclusion/exclusion of two nodes, find the minimum weight vertex cover. Node count and queries up to (10^5), weights up to (10^5).

Recall the duality: minimum weight vertex cover = total weight − maximum weight independent set.

To force a node to be selected in the cover, we exclude it from the independent set by setting its weight to (-\infty) in DP. Conversely, forcing a node to NOT be selected corresponds to adding a huge positive penalty (+\infty) to the independent-set value if that node is chosen. Infeasible scenarios occur when the compuetd cover weight exceeds a large threshold.

All changes are temporary for a single query. We modify the weight, compute the independent-set DP, then restore the original weight. Implementation reuses the same HLD + max-plus matrix framework.

Code Outline

// Matrices, segment tree, HLD identical in structure to the previous problem.
// Duality: min cover = sum - max independent.
void apply_force(int u, bool must_cover) {
    ll new_weight = must_cover ? -INF : INF;
    change(u, new_weight);
}
// After query, revert changes.

Short-Step Data Transmission on a Tree

A tree with vertex weights. Starting at (s), at each step you may jump to a node within distance (k) (1 ≤ k ≤ 3). Find the minimum total weight of visited vertices while reaching (t). (n, Q \le 2\times10^5).

The problem reduces to DP along the unique path (s \to t). DP states depend on (k):

• (k=1): trivial, (f_i = f_{i-1} + w_i).
• (k=2): (f_i = \min(f_{i-1}, f_{i-2}) + w_i).
• (k=3): state tracks distance from the current node: (f_{i,0}, f_{i,1}, f_{i,2}). Let (b_u) be the minimum weight among children of (u). Transitions: [ f_{i,0} = w_i + \min(f_{i-1,0}, f_{i-1,1}, f_{i-1,2}) ] [ f_{i,1} = \min(f_{i-1,0},; f_{i-1,1}+b_{w_i}) ] [ f_{i,2} = f_{i-1,1} ]

These recurrences are captured by min-plus matrix multiplication (analogous to max-plus). For each node a transition matrix is built. To answer queries quickly, we precompute binary-lifting matrices D[u][j] (downward, from top to bottom of a path) and U[u][j] (upward). Query decomposes into three parts: up from (s) to LCA, the LCA itself (with posisble step to its parent), and down from LCA to (t).

Complexity: (O(k^3 (n+q) \log n)).

Matrix Definition and Transitions

struct Mat {
    static const int K = 3;
    ll a[K][K];
    Mat() { for(int i=0;i<K;++i) for(int j=0;j<K;++j) a[i][j]=INF; }
    Mat operator*(const Mat& o) const {
        Mat r;
        for(int i=0;i<K;++i)
            for(int k=0;k<K;++k)
                for(int j=0;j<K;++j)
                    r.a[i][j] = min(r.a[i][j], a[i][k]+o.a[k][j]);
        return r;
    }
};
Mat U[N][L], D[N][L];
// Construction relies on the DP formulas above, for k=1,2,3.

Binary lifting combined with matrix multiplication answers each query in (O(k^3 \log n)). Additional care is needed at the LCA where a step outside the path is allowed.