The problems in this set require careful handling of edge cases and efficient algorithms. Below are the solutions for all four tasks.

T1: Holiday Plan

Given constraints n ≤ 2.5 × 103, an O(n2) approach is feasible.

We enumerate the middle two vertices B and C. For a valid pair (B, C), we pre‑compute the set of possible A (from B) and possible D (from C) using BFS in O(n2).

At least one of A or D can be taken as the best possible value. We examine cases where either A or D is optimal and pick the maximum.

This avoids the complexity of discussing the top three values and only adds a logarithmic factor for sorting.

Time complexity: O(n2 log n)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

const int maxn = 2.5e3 + 5;
const int maxm = 2e4 + 5;

struct Edge {
    int to, nxt;
} edges[maxm];

int n, m, k, edgeCount;
int head[maxn], dist[maxn][maxn];
ll val[maxn];
bool visited[maxn];
vector<int> validVertices[maxn];

bool cmpDesc(int a, int b) { return val[a] > val[b]; }

void addEdge(int u, int v) {
    edgeCount++;
    edges[edgeCount].to = v;
    edges[edgeCount].nxt = head[u];
    head[u] = edgeCount;
}

void bfsDist(int start) {
    queue<int> q;
    memset(dist[start], -1, sizeof(dist[start]));
    memset(visited, false, sizeof(visited));
    visited[start] = true;
    dist[start][start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edges[i].nxt) {
            int v = edges[i].to;
            if (!visited[v]) {
                dist[start][v] = dist[start][u] + 1;
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    ll ans = 0;
    scanf("%d%d%d", &n, &m, &k); k++;
    for (int i = 2; i <= n; i++) scanf("%lld", &val[i]);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) bfsDist(i);
    
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (dist[i][j] >= 1 && dist[i][j] <= k && dist[j][1] >= 1 && dist[j][1] <= k) {
                validVertices[i].push_back(j);
            }
        }
    }
    for (int i = 1; i <= n; i++) sort(validVertices[i].begin(), validVertices[i].end(), cmpDesc);
    
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) {
            if (dist[b][c] <= 0 || dist[b][c] > k || validVertices[b].empty() || validVertices[c].empty()) continue;
            int a = -1, d = -1;
            // try pick a from b best
            for (int idx = 0; idx < (int)validVertices[b].size(); idx++) {
                if (validVertices[b][idx] != c) { a = validVertices[b][idx]; break; }
            }
            if (a != -1) {
                for (int idx = 0; idx < (int)validVertices[c].size(); idx++) {
                    if (validVertices[c][idx] != a && validVertices[c][idx] != b) { d = validVertices[c][idx]; break; }
                }
                if (d != -1) ans = max(ans, val[a] + val[b] + val[c] + val[d]);
            }
            // try pick d from c best
            d = -1; a = -1;
            for (int idx = 0; idx < (int)validVertices[c].size(); idx++) {
                if (validVertices[c][idx] != b) { d = validVertices[c][idx]; break; }
            }
            if (d != -1) {
                for (int idx = 0; idx < (int)validVertices[b].size(); idx++) {
                    if (validVertices[b][idx] != c && validVertices[b][idx] != d) { a = validVertices[b][idx]; break; }
                }
                if (a != -1) ans = max(ans, val[a] + val[b] + val[c] + val[d]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

T2: Strategy Game

This is a straightforward problem solved by case analysis.

1. First player picks a positive number.

   1. If second player has a negative number: second picks the smallest negative, first picks the smallest positive.
   2. If second player has zero: second picks 0.
   3. If second player has only positive numbers: second picks the smallest positive, first picks the largest positive.

2. First player picks a negative number.

   1. If second player has a positive number: first picks the largest negative, second picks the largest positive.
   2. If second player has zero: second picks 0.
   3. If second player has only negative numbers: first picks the smallest negative, second picks the largest neagtive.

3. First player picks zero: the product is 0.

Since the first player is optimal, they choose best among the three possibilities. Use RMQ to maintain the required extremes in each interval.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;
const int logSz = 20;
const ll INF = 1e18;

int q;
int lg[maxn];
int prefixZeroA[maxn], prefixZeroB[maxn];

inline int maxNonZero(int x, int y) {
    if (x == 0) return y;
    if (y == 0) return x;
    return max(x, y);
}
inline int minNonZero(int x, int y) {
    if (x == 0) return y;
    if (y == 0) return x;
    return min(x, y);
}

struct RMQArray {
    int size;
    int arr[maxn];
    int maxPos[logSz][maxn], minPos[logSz][maxn];
    int maxNeg[logSz][maxn], minNeg[logSz][maxn];

    void init() {
        for (int i = 1; i <= size; i++) {
            if (arr[i] > 0) {
                maxPos[0][i] = minPos[0][i] = arr[i];
                maxNeg[0][i] = minNeg[0][i] = 0;
            } else if (arr[i] < 0) {
                maxNeg[0][i] = minNeg[0][i] = arr[i];
                maxPos[0][i] = minPos[0][i] = 0;
            } else {
                maxPos[0][i] = minPos[0][i] = 0;
                maxNeg[0][i] = minNeg[0][i] = 0;
            }
        }
        for (int j = 1; (1 << j) <= size; j++) {
            for (int i = 1; i + (1 << j) - 1 <= size; i++) {
                maxPos[j][i] = maxNonZero(maxPos[j-1][i], maxPos[j-1][i + (1 << (j-1))]);
                minPos[j][i] = minNonZero(minPos[j-1][i], minPos[j-1][i + (1 << (j-1))]);
                maxNeg[j][i] = maxNonZero(maxNeg[j-1][i], maxNeg[j-1][i + (1 << (j-1))]);
                minNeg[j][i] = minNonZero(minNeg[j-1][i], minNeg[j-1][i + (1 << (j-1))]);
            }
        }
    }

    int queryMaxPos(int l, int r) {
        int k = lg[r - l + 1];
        return maxNonZero(maxPos[k][l], maxPos[k][r - (1 << k) + 1]);
    }
    int queryMinPos(int l, int r) {
        int k = lg[r - l + 1];
        return minNonZero(minPos[k][l], minPos[k][r - (1 << k) + 1]);
    }
    int queryMaxNeg(int l, int r) {
        int k = lg[r - l + 1];
        return maxNonZero(maxNeg[k][l], maxNeg[k][r - (1 << k) + 1]);
    }
    int queryMinNeg(int l, int r) {
        int k = lg[r - l + 1];
        return minNonZero(minNeg[k][l], minNeg[k][r - (1 << k) + 1]);
    }
} A, B;

ll solveFirstPositive(int l, int r, int s, int t) {
    int minPosA = A.queryMinPos(l, r);
    if (minPosA == 0) return -INF;
    int maxPosA = A.queryMaxPos(l, r);
    int minNegB = B.queryMinNeg(s, t);
    if (minNegB != 0) return 1LL * minPosA * minNegB;
    if (prefixZeroB[t] - prefixZeroB[s-1] > 0) return 0;
    int minPosB = B.queryMinPos(s, t);
    if (minPosB != 0) return 1LL * maxPosA * minPosB;
    return 0;
}

ll solveFirstNegative(int l, int r, int s, int t) {
    int maxNegA = A.queryMaxNeg(l, r);
    if (maxNegA == 0) return -INF;
    int minNegA = A.queryMinNeg(l, r);
    int maxPosB = B.queryMaxPos(s, t);
    if (maxPosB != 0) return 1LL * maxNegA * maxPosB;
    if (prefixZeroB[t] - prefixZeroB[s-1] > 0) return 0;
    int maxNegB = B.queryMaxNeg(s, t);
    if (maxNegB != 0) return 1LL * minNegA * maxNegB;
    return 0;
}

int main() {
    scanf("%d%d%d", &A.size, &B.size, &q);
    for (int i = 2; i <= max(A.size, B.size); i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= A.size; i++) {
        scanf("%d", &A.arr[i]);
        prefixZeroA[i] = prefixZeroA[i-1] + (A.arr[i] == 0);
    }
    for (int i = 1; i <= B.size; i++) {
        scanf("%d", &B.arr[i]);
        prefixZeroB[i] = prefixZeroB[i-1] + (B.arr[i] == 0);
    }
    A.init(); B.init();
    while (q--) {
        int l, r, s, t;
        scanf("%d%d%d%d", &l, &r, &s, &t);
        ll ans1 = solveFirstPositive(l, r, s, t);
        ll ans2 = solveFirstNegative(l, r, s, t);
        ll ans = max(ans1, ans2);
        if (prefixZeroA[r] - prefixZeroA[l-1] > 0) ans = max(ans, 0LL);
        printf("%lld\n", ans);
    }
    return 0;
}

T3: Star Wars

We use a clever hashing technique.

Condition 2 implies we have exactly n directed edges, each vertex has out‑degree 1. Thus the graph is a forest of inward base‑cycle trees, automatically satisfying condition 1.

Let S be the multiset of source vertices of all existing edges. We maintain a hash of S and compare it with the hash of the multiset of a valid inward base‑cycle tree. This allows O(1) verification per query.

For operations 1 and 3 (adding/removing a single edge), update the hash directly. For operations 2 and 4 (removing/restoring all edges incident to a vertex), we first pre‑compute the contribution of each vertex to the hash in the initial graph, and then maintain the current contribution. Operation 2 subtracts the current contribution, operation 4 restores the pre‑computed contribution.

We use a simple hash: sum of vertex indices and XOR of vertex indices. Optionally, we can add sum of squares for safety.

Time complexity: O(n + m)

#include <cstdio>
using namespace std;

typedef long long ll;

const int maxn = 5e5 + 5;
const int maxm = 5e5 + 5;

int n, m, q;
int u[maxm], v[maxm];
ll curSum = 0, targetSum;
int curXor = 0, targetXor;
ll contribSum[maxn], originalSum[maxn];
int contribXor[maxn], originalXor[maxn];

int main() {
    scanf("%d%d", &n, &m);
    targetSum = 1LL * n * (n + 1) / 2;
    targetXor = 0;
    for (int i = 1; i <= n; i++) targetXor ^= i;

    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u[i], &v[i]);
        curSum += u[i];
        curXor ^= u[i];
        contribSum[v[i]] += u[i];
        contribXor[v[i]] ^= u[i];
    }
    for (int i = 1; i <= n; i++) {
        originalSum[i] = contribSum[i];
        originalXor[i] = contribXor[i];
    }

    scanf("%d", &q);
    while (q--) {
        int opt, a, b;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d", &a, &b);
            // remove edge a->b
            contribSum[b] -= a;
            contribXor[b] ^= a;
            curSum -= a;
            curXor ^= a;
        } else if (opt == 2) {
            scanf("%d", &b);
            // remove all edges entering b
            curSum -= contribSum[b];
            curXor ^= contribXor[b];
            contribSum[b] = 0;
            contribXor[b] = 0;
        } else if (opt == 3) {
            scanf("%d%d", &a, &b);
            // add edge a->b
            contribSum[b] += a;
            contribXor[b] ^= a;
            curSum += a;
            curXor ^= a;
        } else { // opt == 4
            scanf("%d", &b);
            // restore all edges entering b
            curSum += (originalSum[b] - contribSum[b]);
            curXor ^= (originalXor[b] ^ contribXor[b]);
            contribSum[b] = originalSum[b];
            contribXor[b] = originalXor[b];
        }
        puts((curSum == targetSum && curXor == targetXor) ? "YES" : "NO");
    }
    return 0;
}

T4: Data Transmission

We combine binary lifting with matrix multiplication to speed up tree DP.

First, obtain 76 points by extracting the tree path and performing linear DP. For full solution we optimise with doubling.

Since the queries are static, we use binary lifting (or heavy‑light decomposition for dynamic).

We define a DP on the path. Let fi be the minimum cost to reach the i‑th vertex on the path. The transition can be expressed as a matrix multiplication when we allow jumping up to k steps back. For k = 3, the state vector is [fi−1, fi−2, fi−3] and the target is [fi, fi−1, fi−2]. The tarnsition matrix is:

Time complexity: O(33 n log n)

#include <cstdio>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for (int i = a; i <= b; i++)

typedef long long ll;

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;
const int logSz = 20;
const ll INF = 1e18;

struct Edge {
    int to, nxt;
} edges[maxm];

struct Matrix {
    int rows, cols;
    ll w[3][3];
    Matrix operator * (const Matrix& rhs) const {
        Matrix res;
        res.rows = rows;
        res.cols = rhs.cols;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                res.w[i][j] = INF;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                for (int k = 0; k < cols; k++) // assuming m == cols
                    res.w[i][j] = min(res.w[i][j], w[i][k] + rhs.w[k][j]);
        return res;
    }
} baseMatrix, vertexMat[maxn], upMat[maxn][logSz], downMat[maxn][logSz];

int n, queryCount, k, edgeCount;
int head[maxn], weight[maxn], depth[maxn], parent[maxn][logSz];

void addEdge(int u, int v) {
    edgeCount++;
    edges[edgeCount].to = v;
    edges[edgeCount].nxt = head[u];
    head[u] = edgeCount;
}

void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1;
    parent[u][0] = fa;
    if (k == 3) {
        // find minimum weight among neighbours (excluding parent)
        ll minNeigh = INF;
        for (int i = head[u]; i; i = edges[i].nxt) {
            int v = edges[i].to;
            if (v != fa) minNeigh = min(minNeigh, (ll)weight[v]);
        }
        if (minNeigh != INF) vertexMat[u].w[1][1] = min(vertexMat[u].w[1][1], minNeigh);
    }
    upMat[u][0] = vertexMat[fa];
    downMat[u][0] = vertexMat[u];
    for (int i = 1; i <= 19; i++) {
        int mid = parent[u][i-1];
        parent[u][i] = parent[mid][i-1];
        upMat[u][i] = upMat[u][i-1] * upMat[mid][i-1];
        downMat[u][i] = downMat[mid][i-1] * downMat[u][i-1];
    }
    for (int i = head[u]; i; i = edges[i].nxt) {
        int v = edges[i].to;
        if (v != fa) dfs(v, u);
    }
}

Matrix solve(int u, int v) {
    Matrix a = baseMatrix, b = baseMatrix;
    if (depth[u] > depth[v]) {
        for (int i = 19; i >= 0; i--) {
            if (depth[parent[u][i]] >= depth[v]) {
                a = a * upMat[u][i];
                u = parent[u][i];
            }
        }
    }
    if (depth[v] > depth[u]) {
        for (int i = 19; i >= 0; i--) {
            if (depth[parent[v][i]] >= depth[u]) {
                b = downMat[v][i] * b;
                v = parent[v][i];
            }
        }
    }
    if (u == v) return a * b;
    for (int i = 19; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            a = a * upMat[u][i];
            b = downMat[v][i] * b;
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return a * upMat[u][0] * downMat[v][0] * b;
}

int main() {
    scanf("%d%d%d", &n, &queryCount, &k);
    baseMatrix = {k, k, {{0, INF, INF}, {INF, 0, INF}, {INF, INF, 0}}};
    for (int i = 1; i <= n; i++) {
        scanf("%d", &weight[i]);
        vertexMat[i] = {k, k, {{INF, INF, INF}, {INF, INF, INF}, {INF, INF, INF}}};
        for (int j = 0; j <= k-1; j++) vertexMat[i].w[j][0] = weight[i];
        for (int j = 1; j <= k-1; j++) vertexMat[i].w[j-1][j] = 0;
    }
    for (int i = 1; i <= n-1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs(1, 0);
    while (queryCount--) {
        int u, v;
        scanf("%d%d", &u, &v);
        Matrix start = {1, k, {(ll)weight[u], INF, INF}};
        ll res = (start * solve(u, v)).w[0][0];
        printf("%lld\n", res);
    }
    return 0;
}