Determining Valid Initial Values for Tree Path Constraints

Let v represent the cumulative change in value from the root to a specific node u. For the initial value x to remain valid when reaching u, it must satisfy the constraint L_u - v <= x <= R_u - v. The cumulative change v can be managed efficiently by mapping the tree to a flat array using an Euler Tour (DFS entry and exit times). Subtree additions or subtractions then translate directly to range updates on this flat array.

A Fenwick Tree (Binary Indexed Tree) supporting range updates and point queries is an optimal choice for computing v at each node. Once the absolute ranges [L', R'] are established for every node, a second DFS propagates the intersection of these valid intervals down the tree, ensuring that the initial value satisfies all ancestral constraints. Since the domain of x is large, coordinate compression is applied to all interval bounds and queries, followed by a difference array to calculate the number of valid starting values.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

class Fenwick {
    vector<ll> tree;
    int sz;
public:
    Fenwick(int n) : sz(n), tree(n + 1, 0) {}
    void modify(int i, ll v) { for (; i <= sz; i += i & -i) tree[i] += v; }
    void range_add(int l, int r, ll v) { modify(l, v); modify(r + 1, -v); }
    ll query(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }
};

const ll INF = 1e18;
int dfs_timer = 0;
vector<int> entry, subtree_sz;
vector<ll> low, high;
vector<vector<int>> adj;

void calc_dfs(int u, int p) {
    entry[u] = ++dfs_timer;
    subtree_sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            calc_dfs(v, u);
            subtree_sz[u] += subtree_sz[v];
        }
    }
}

void prop_dfs(int u, int p, ll cur_L, ll cur_R) {
    low[u] = max(low[u], cur_L);
    high[u] = min(high[u], cur_R);
    for (int v : adj[u]) {
        if (v != p) prop_dfs(v, u, low[u], high[u]);
    }
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    adj.resize(n + 1); entry.resize(n + 1); subtree_sz.resize(n + 1);
    low.resize(n + 1); high.resize(n + 1);
    low[1] = -INF; high[1] = INF;

    for (int i = 2; i <= n; ++i) {
        int p; ll a, b;
        scanf("%d%lld%lld", &p, &a, &b);
        adj[p].push_back(i);
        adj[i].push_back(p);
        low[i] = a; high[i] = b;
    }
    calc_dfs(1, 0);

    Fenwick bit(n);
    for (int i = 1; i <= n; ++i) {
        char op; ll x;
        scanf(" %c%lld", &op, &x);
        if (subtree_sz[i] == 1) continue;
        ll delta = (op == '+') ? x : -x;
        bit.range_add(entry[i] + 1, entry[i] + subtree_sz[i] - 1, delta);
    }

    for (int i = 2; i <= n; ++i) {
        ll v = bit.query(entry[i]);
        low[i] -= v; high[i] -= v;
    }

    prop_dfs(1, 0, -INF, INF);

    vector<ll> coords;
    for (int i = 2; i <= n; ++i) {
        coords.push_back(low[i]);
        coords.push_back(high[i]);
    }
    vector<ll> queries(q + 1);
    for (int i = 1; i <= q; ++i) {
        scanf("%lld", &queries[i]);
        coords.push_back(queries[i]);
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int m = coords.size();

    auto get_idx = [&](ll val) {
        return lower_bound(coords.begin(), coords.end(), val) - coords.begin() + 1;
    };

    vector<ll> diff(m + 2, 0);
    for (int i = 2; i <= n; ++i) {
        if (low[i] > high[i]) continue;
        int l = get_idx(low[i]);
        int r = get_idx(high[i]);
        diff[l]++;
        diff[r + 1]--;
    }

    for (int i = 1; i <= m; ++i) diff[i] += diff[i - 1];

    for (int i = 1; i <= q; ++i) {
        printf("%lld\n", diff[get_idx(queries[i])] + 1);
    }
    return 0;
}

Finding the Minimum Weight Edge Cut via Maximum Spanning Tree

Minimizing the weight of removed edges to separate two designated nodes is equivalent to maximizing the weight of the remaining edges, provided the two nodes remain disconnected. This can be solved using a variant of Kruskal's algorithm. Sort all edges in descending order of weight. Initialize a Disjoint Set Union (DSU) structure, tracking whether each component contains either of the two forbidden nodes.

Iterate through the sorted edges. For each edge, check if its endpoints belong to different components. If merging these components would connect the two forbidden nodes, skip the edge (conceptually removing it). Otherwise, merge the components and add the edge's weight to the maximum spanning tree sum. The final answer is the total weight of all edges minus the sum of the included edges.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Edge {
    int u, v;
    ll w;
    bool operator<(const Edge& o) const { return w > o.w; }
};

class DSU {
    vector<int> par, rnk;
    vector<bool> has_a, has_b;
public:
    DSU(int n, int a, int b) : par(n + 1), rnk(n + 1, 0), has_a(n + 1, false), has_b(n + 1, false) {
        for (int i = 1; i <= n; ++i) par[i] = i;
        has_a[a] = true; has_b[b] = true;
    }
    int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
    bool can_unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        return !((has_a[rx] && has_b[ry]) || (has_b[rx] && has_a[ry]));
    }
    void merge(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rnk[rx] < rnk[ry]) swap(rx, ry);
        par[ry] = rx;
        rnk[rx] += rnk[ry];
        has_a[rx] = has_a[rx] || has_a[ry];
        has_b[rx] = has_b[rx] || has_b[ry];
    }
};

int main() {
    int n, m, a, b;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    vector<Edge> edges(m);
    ll total = 0;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%lld", &edges[i].u, &edges[i].v, &edges[i].w);
        total += edges[i].w;
    }
    sort(edges.begin(), edges.end());
    DSU dsu(n, a, b);
    ll mst_sum = 0;
    for (auto& e : edges) {
        if (dsu.can_unite(e.u, e.v)) {
            dsu.merge(e.u, e.v);
            mst_sum += e.w;
        }
    }
    printf("%lld\n", total - mst_sum);
    return 0;
}

Counting Geometric Patterns in Binary Grids using Suffix Sums

To count 'C' and 'F' shapes within a binary grid, precompute the maximum extensions of empty cells to the right and downwards. For any cell (i, j), let right[i][j] be the number of consecutive empty cells to the right, and down[i][j] be the number of consecutive empty cells below. Fix the top-left corner of the shape at (i, j). A 'C' shape requires a bottom horizontal bar at some row x in the range [i + 2, i + down[i][j]].

The number of 'C' configurations is the product of the right extensions of the top and bottom bars. Summing over all valid rows x gives right[i][j] * sum(right[x][j]). By maintaining column-wise suffix sums of right, this summation can be resolved in O(1). For the 'F' shape, a vertical line extends downwards from the bottom bar. The count becomes right[i][j] * sum(right[x][j] * down[x][j]), which is similarly optimized using suffix sums of the product of right and down extensions.

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
    int t, id;
    scanf("%d%d", &t, &id);
    while (t--) {
        int n, m, c_req, f_req;
        scanf("%d%d%d%d", &n, &m, &c_req, &f_req);
        vector<vector<char>> grid(n + 2, vector<char>(m + 2));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf(" %c", &grid[i][j]);

        vector<vector<ll>> r_len(n + 2, vector<ll>(m + 2, 0));
        vector<vector<ll>> d_len(n + 2, vector<ll>(m + 2, 0));
        vector<vector<ll>> suf_r(n + 2, vector<ll>(m + 2, 0));
        vector<vector<ll>> suf_rd(n + 2, vector<ll>(m + 2, 0));

        for (int i = 1; i <= n; ++i) {
            for (int j = m - 1; j >= 1; --j) {
                if (grid[i][j] == '0' && grid[i][j + 1] == '0')
                    r_len[i][j] = r_len[i][j + 1] + 1;
                else
                    r_len[i][j] = 0;
            }
        }

        for (int j = 1; j <= m; ++j) {
            for (int i = n - 1; i >= 1; --i) {
                if (grid[i][j] == '0' && grid[i + 1][j] == '0')
                    d_len[i][j] = d_len[i + 1][j] + 1;
                else
                    d_len[i][j] = 0;
            }
        }

        for (int j = 1; j <= m; ++j) {
            for (int i = n; i >= 1; --i) {
                suf_r[i][j] = (suf_r[i + 1][j] + r_len[i][j]) % MOD;
                suf_rd[i][j] = (suf_rd[i + 1][j] + (r_len[i][j] * d_len[i][j]) % MOD) % MOD;
            }
        }

        ll c_cnt = 0, f_cnt = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i][j] == '1') continue;
                int top = i + 2, bot = i + d_len[i][j];
                if (top > bot) continue;
                c_cnt = (c_cnt + r_len[i][j] % MOD * ((suf_r[top][j] - suf_r[bot + 1][j] + MOD) % MOD) % MOD) % MOD;
                f_cnt = (f_cnt + r_len[i][j] % MOD * ((suf_rd[top][j] - suf_rd[bot + 1][j] + MOD) % MOD) % MOD) % MOD;
            }
        }

        ll ans_c = c_req ? c_cnt : 0;
        ll ans_f = f_req ? f_cnt : 0;
        printf("%lld %lld\n", ans_c, ans_f);
    }
    return 0;
}