Problem 1: Counting Valid Pairs with LCM Condition

Problem Description

Given an integer n where 1 ≤ n ≤ 10^8, determine the number of pairs (x, y) such that 1 ≤ x, y ≤ n and the following inequality holds:

lcm(x, y) / gcd(x, y) ≤ 3

Note that lcm(x, y) = (x * y) / gcd(x, y)^2.

Solution Approach

This is a straightforward number theory problem. Let d = gcd(x, y). We can express x and y as x = d * a and y = d * b, where gcd(a, b) = 1. Substituting these into the inequality simplifies the condition to:

a * b ≤ 3

Since a and b are coprime positive integers, the valid combinations for (a, b) are limited to (1, 1), (1, 2), (2, 1), (1, 3), and (3, 1). We can iterate through these coprime pairs and count how many multiples d fit within the limit n for each pair.

Problem 2: Connected Subgraphs After Edge Removal

Problem Description

Given a tree with n nodes (1 ≤ n ≤ 5 × 10^5) and n-1 edges, for each edge i connecting (u_i, v_i), calculate the number of non-empty connected subgraphs in the two components formed after removing that edge. Return results modulo 998244353.

Solution Approach

We solve this using Tree DP with Re-rooting.

1. Standard DP: Define dp[node][0] as the number of non-empty connected subgraphs in the subtree where node is not selected. Define dp[node][1] as the count where node is selected.
   • dp[node][0] = Σ (dp[child][0] + dp[child][1])
   • dp[node][1] = Π (1 + dp[child][1])
2. Re-rooting: When we cut an edge between a parent p and child c, the answer for the c side is simply dp[c][0] + dp[c][1]. To find the answer for the p side, we must remove the contribution of c from p and consider the rest of the tree as a new "subtree" for p.
3. Handling Modulo Division: Since dp[p][0] + 1 might be a multiple of the modulus, we cannot use modular inverse to remove the child's contribution. Instead, we maintain prefix and suffix products of the children's factors (1 + dp[child][1]) to compute the product excluding a specific child efficiently.

Implementation

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 5e5 + 10, MOD = 998244353;

struct Edge {
    int to, id, next;
} graph[MAXN * 2];
int head[MAXN], edge_idx;
int dp[MAXN][2], reroot[MAXN][2];

struct Result {
    int u, v, ans_u, ans_v;
} res[MAXN];
vector<int> pref[MAXN], suff[MAXN];

int power(int base, int exp) {
    int result = 1;
    while (exp) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void addEdge(int u, int v, int id) {
    graph[++edge_idx] = {v, id, head[u]};
    head[u] = edge_idx;
}

void dfsDown(int node, int parent) {
    dp[node][1] = 1;
    for (int i = head[node]; i; i = graph[i].next) {
        int child = graph[i].to;
        if (child == parent) continue;
        dfsDown(child, node);
        dp[node][0] = (dp[node][0] + dp[child][0] + dp[child][1]) % MOD;
        int factor = (1 + dp[child][1]) % MOD;
        dp[node][1] = dp[node][1] * factor % MOD;
        pref[node].push_back(factor);
        suff[node].push_back(factor);
    }
    // Build prefix and suffix products
    for (int i = suff[node].size() - 2; i >= 0; i--)
        suff[node][i] = suff[node][i + 1] * suff[node][i] % MOD;
    for (int i = 1; i < pref[node].size(); i++)
        pref[node][i] = pref[node][i - 1] * pref[node][i] % MOD;
    suff[node].push_back(1);
}

void dfsUp(int node, int parent, int parentFactor, int edgeId) {
    int p0 = 0, p1 = parentFactor;
    if (node != 1) {
        // Remove current node's contribution from parent's reroot state
        p0 = (reroot[parent][0] - (dp[node][0] + dp[node][1]) + MOD) % MOD;
        p1 = ((1 + parentFactor) * (edgeId > 0 ? pref[parent][edgeId - 1] : 1) % MOD) * suff[parent][edgeId + 1] % MOD;
        reroot[node][0] = (dp[node][0] + p0 + p1) % MOD;
        reroot[node][1] = dp[node][1] * (1 + p1) % MOD;
    } else {
        reroot[node][1] = dp[node][1];
        reroot[node][0] = dp[node][0];
        p1 = 0;
    }

    int childIdx = 0;
    for (int i = head[node]; i; i = graph[i].next) {
        int child = graph[i].to;
        if (child == parent) continue;
        
        int childAns = (dp[child][0] + dp[child][1]) % MOD;
        int parentSideAns = 0;
        
        // Calculate contribution of node without current child
        int nodeWithoutChild0 = (reroot[node][0] - (dp[child][0] + dp[child][1]) + MOD) % MOD;
        int nodeWithoutChild1 = ((1 + p1) * (childIdx > 0 ? pref[node][childIdx - 1] : 1) % MOD) * suff[node][childIdx + 1] % MOD;
        parentSideAns = (nodeWithoutChild0 + nodeWithoutChild1) % MOD;

        if (node == res[graph[i].id].u) {
            res[graph[i].id].ans_u = parentSideAns;
            res[graph[i].id].ans_v = childAns;
        } else {
            res[graph[i].id].ans_u = childAns;
            res[graph[i].id].ans_v = parentSideAns;
        }
        
        dfsUp(child, node, nodeWithoutChild1, childIdx);
        childIdx++;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        addEdge(x, y, i); addEdge(y, x, i);
        res[i] = {x, y, 0, 0};
    }
    dfsDown(1, 0);
    dfsUp(1, 0, 0, 0);
    for (int i = 1; i < n; i++) cout << res[i].ans_u << " " << res[i].ans_v << "\n";
    return 0;
}

Problem 3: Reaching Non-Critical Nodes via Key Points

Problem Description

Givan an undirected graph with n nodes and m weighted edges. Nodes 1 to c are "Key Points". Walking an edge consumes energy equal to its weight. If energy drops below the weight, the edge cannot be traversed. However, arriving at any Key Point restores energy to r.

Count how many non-critical nodes (nodes > c) can be reached starting from a Key Point, traversing a path that visits at least k distinct Key Points.

Solution Approach

1. Key Point Connectivity: Two Key Points are mutually reachable if the shortest path between them is ≤ r. We need to group Key Points into clusters where internal distances are ≤ r.
2. Clustering:
   • Run Dijkstra starting from all Key Points (initial distance 0). Track which Key Point is closest to each node (source[node]).
   • For every edge (u, v, w), if dist[u] + w + dist[v] ≤ r, the Key Points source[u] and source[v] are in the same cluster. Use Union-Find to merge them.
3. Counting Valid Clusters: Only clusters with size ≥ k are valid targets.
4. Final Reachability: Reset distances. Run Dijkstra again starting only from Key Points belonging to valid (size ≥ k) clusters. A non-critical node is reachable if its final distance is ≤ r.

Implementation

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;

const int N = 1e5 + 10, M = 5e5 + 10;
const int INF = 1e18;

int n, m, c, r, k, parent[N], sz[N], dist[N], visited[N], origin[N];
struct Edge { int v, w, next; } edges[M * 2];
int head[N], idx;

void addEdge(int u, int v, int w) {
    edges[++idx] = {v, w, head[u]};
    head[u] = idx;
}

int find(int x) { return parent[x] = (x == parent[x] ? x : find(parent[x])); }
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) { parent[fx] = fy; sz[fy] += sz[fx]; }
}

void buildClusters() {
    fill(dist, dist + N, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i <= c; i++) dist[i] = 0, pq.push({0, i}), origin[i] = i;
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue; visited[u] = 1;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].v;
            if (!visited[v] && d + edges[i].w <= r && dist[v] > d + edges[i].w) {
                dist[v] = d + edges[i].w;
                origin[v] = origin[u];
                pq.push({dist[v], v});
            }
        }
    }
    for (int u = 1; u <= n; u++)
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].v;
            if (dist[u] + edges[i].w + dist[v] <= r) unite(origin[u], origin[v]);
        }
}

void computeAnswer() {
    fill(dist, dist + N, INF);
    fill(visited, visited + N, 0);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i <= c; i++) 
        if (sz[find(i)] >= k) dist[i] = 0, pq.push({0, i});
        
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue; visited[u] = 1;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].v;
            if (edges[i].w > r) continue;
            if (!visited[v] && dist[v] > d + edges[i].w) {
                dist[v] = d + edges[i].w;
                pq.push({dist[v], v});
            }
        }
    }
    int count = 0;
    for (int i = c + 1; i <= n; i++) if (dist[i] <= r) count++;
    cout << count << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> c >> r >> k;
    for (int i = 1; i <= m; i++) {
        int x, y, w; cin >> x >> y >> w;
        addEdge(x, y, w); addEdge(y, x, w);
    }
    for (int i = 1; i <= n; i++) parent[i] = i, sz[i] = 1;
    buildClusters();
    computeAnswer();
    return 0;
}

Problem 4: Offline Queue Operations and Queries

Problem Description

We have n queues. There are q operations and queries:

1. Add: In queues [L, R], add cnt people of type type.
2. Clear: In queues [L, R], remove cnt people (or clear).
3. Query: At queue pos, ask: if you pick the k-th person in the current queue (ordered by time of operation), what is their type?

Solution Approach

We use offline processing with two Segment Trees.

1. Scan Queues: Iterate through queues 1 to n. An operation affects queue i if L ≤ i ≤ R. We can treat operations as appearing at index L and disappearing at index R+1.
2. Segment Tree 1 (AddTree): Maintains the sum of additions over time [1, q]. It supports point updates (adding to a timestamp) and binary searching for the k-th person (finding the timestamp where cumulative sum meets k).
3. Segment Tree 2 (MinTree): Maintains Fsum[t], the cumulative sum of operations (including removals) up to time t.
   • The minimum value of Fsum in range [1, t] represents the "clear point" (the lowest state before time t).
   • If a query asks for the k-th person, we calculate effective_k = k + (current_state - min_state). We then search for this effective_k in AddTree.

Implementation

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 10;

namespace AddTree {
    int sum[N * 4], label[N * 4];
    void pushup(int id) { sum[id] = sum[id*2] + sum[id*2+1]; }
    void update(int id, int l, int r, int pos, int val, int type) {
        if (l == r) { sum[id] += val; label[id] = type; return; }
        int mid = (l + r) / 2;
        if (pos <= mid) update(id*2, l, mid, pos, val, type);
        else update(id*2+1, mid+1, r, pos, val, type);
        pushup(id);
    }
    int querySum(int id, int l, int r, int R) {
        if (r <= R) return sum[id];
        int mid = (l + r) / 2;
        if (R <= mid) return querySum(id*2, l, mid, R);
        return querySum(id*2, l, mid, R) + querySum(id*2+1, mid+1, r, R);
    }
    int findKth(int id, int l, int r, int k) {
        if (l == r) return label[id];
        int mid = (l + r) / 2;
        if (sum[id*2] >= k) return findKth(id*2, l, mid, k);
        return findKth(id*2+1, mid+1, r, k - sum[id*2]);
    }
}

namespace MinTree {
    int mn[N * 4], lazy[N * 4];
    void pushup(int id) { mn[id] = min(mn[id*2], mn[id*2+1]); }
    void addTag(int id, int v) { mn[id] += v; lazy[id] += v; }
    void pushdown(int id) {
        if (!lazy[id]) return;
        addTag(id*2, lazy[id]); addTag(id*2+1, lazy[id]);
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int pos, int val) {
        if (l >= pos) { addTag(id, val); return; }
        pushdown(id);
        int mid = (l + r) / 2;
        if (pos <= mid) update(id*2, l, mid, pos, val), addTag(id*2+1, val);
        else update(id*2+1, mid+1, r, pos, val);
        pushup(id);
    }
    int queryMin(int id, int l, int r, int R) {
        if (r <= R) return mn[id];
        pushdown(id);
        int mid = (l + r) / 2;
        if (R <= mid) return queryMin(id*2, l, mid, R);
        return min(queryMin(id*2, l, mid, R), queryMin(id*2+1, mid+1, r, R));
    }
    int queryPoint(int id, int l, int r, int pos) {
        if (l == r) return mn[id];
        pushdown(id);
        int mid = (l + r) / 2;
        if (pos <= mid) return queryPoint(id*2, l, mid, pos);
        return queryPoint(id*2+1, mid+1, r, pos);
    }
}

int n, m, q, tot, ans[N];
struct Event { int time, val, type; };
vector<Event> addOps[N], remOps[N], queries[N];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        int opt, a, b, v1, v2; cin >> opt >> a >> b;
        if (opt == 1) {
            cin >> v1 >> v2;
            addOps[a].push_back({i, v2, v1});
            addOps[b + 1].push_back({i, -v2, v1});
        } else if (opt == 2) {
            cin >> v1;
            remOps[a].push_back({i, -v1, 0});
            remOps[b + 1].push_back({i, v1, 0});
        } else {
            queries[a].push_back({i, b, ++tot});
        }
    }

    for (int t = 1; t <= n; t++) {
        for (auto &e : addOps[t]) {
            AddTree::update(1, 1, q, e.time, e.val, e.type);
            MinTree::update(1, 1, q, e.time, e.val);
        }
        for (auto &e : remOps[t]) {
            MinTree::update(1, 1, q, e.time, e.val);
        }
        for (auto &e : queries[t]) {
            int total = AddTree::querySum(1, 1, q, e.time);
            int preMin = min(0LL, MinTree::queryMin(1, 1, q, e.time));
            int currVal = MinTree::queryPoint(1, 1, q, e.time);
            if (e.val <= currVal - preMin) {
                ans[e.type] = AddTree::findKth(1, 1, q, total - (currVal - preMin) + e.val);
            }
        }
    }
    for (int i = 1; i <= tot; i++) cout << ans[i] << "\n";
    return 0;
}