You are given an undirected connected graph with $$$n$$$ nodes labeled from $$$0$$$ to $$$n - 1$$$ and a 2D integer array edges where $$$edges[i] = [u_i, v_i, w_i]$$$ denotes an undirected edge between node $$$u_i$$$ and node $$$v_i$$$ with weight $$$w_i$$$, and an integer $$$k$$$.

You are allowed to remove any number of edges from the graph such that the resulting graph has at most k connected components.

The cost of a component is defined as the maximum edge weight in that component. If a component has no edges, its cost is $$$0$$$.

Return the minimum possible value of the maximum cost among all components after such removals.

• $$$1 ≤ n ≤ 5 * 10^4$$$

• $$$0 ≤ edges.length ≤ 10^5$$$

• $$$edges[i].length == 3$$$

• $$$0 ≤ u_i, v_i \lt n$$$

• $$$1 ≤ w_i ≤ 10^6$$$

• $$$1 ≤ k ≤ n$$$

• The input graph is connected.

You are given an integer array $$$nums$$$ of size $$$n$$$ containing only $$$+1$$$ and $$$-1$$$, and an integer $$$k$$$.

You can perform the following operation at most $$$k$$$ times:
$$$·$$$ Choose an index $$$i$$$ $$$(0 ≤ i \lt n - 1)$$$, and multiply both $$$nums[i]$$$ and $$$nums[i + 1]$$$ by $$$-1$$$.

Note that you can choose the same index $$$i$$$ more than once in different operations.

Return $$$true$$$ if it is possible to make all elements of the array equal after at most $$$k$$$ operations, and $$$false$$$ otherwise.

Input: $$$nums = [1,-1,1,-1,1], k = 3$$$

Output: $$$true$$$

Explanation:

We can make all elements in the array equal in $$$2$$$ operations as follows:
$$$·$$$ Choose index $$$i = 1$$$, and multiply both $$$nums[1]$$$ and $$$nums[2]$$$ by $$$-1$$$. Now $$$nums = [1,1,-1,-1,1]$$$.
$$$·$$$ Choose index $$$i = 2$$$, and multiply both $$$nums[2]$$$ and $$$nums[3]$$$ by $$$-1$$$. Now $$$nums = [1,1,1,1,1]$$$.

$$$·$$$ $$$1 ≤ n ≤ 10^{5}$$$
$$$·$$$ $$$nums[i]$$$ is either $$$-1$$$ or $$$+1$$$.
$$$·$$$ $$$1 ≤ k ≤ n$$$

constexpr int N = 100000; int temp[N];

class Solution {
public:
    bool canMakeEqual(const std::vector<int>& nums, int k) {
        int n = nums.size();
        auto check = [&](int t) -> bool {
            int ops = 0;
            std::copy(nums.begin(), nums.end(), temp);
            for (int idx = 0; idx + 1 < n; ++idx) {
                if (temp[idx] == -t) {
                    ++ops;
                    temp[idx + 0] *= -1;
                    temp[idx + 1] *= -1;
                }
            }
            return ops <= k && temp[n - 1] == t;
        };
        return check(-1) || check(+1);
    }
};

• Every operation results in flipping of two elements.
• So if any subarray $$$[L, R]$$$ has
• • Odd number of $$$+1/-1$$$, we can never make the entire subarray containing $$$+1/-1$$$ respectively.

It would be possible to convert the entire subarray to $$$-1$$$ or $$$+1$$$ if there are even occurences of it (despite odd occurences of the other value). We just need to check if the number of operations taken is $$$k$$$ or less.

Now, lets consider a subarray $$$[L, R]$$$ containing an even number of $$$-1$$$'s (lets say 4) at indices $$$p, q, r, s$$$, where $$$p \lt q \lt r \lt s$$$.

The greedy strategy for doing this would be to:

• Take adjacent pairs $$$(p, q)$$$, $$$(r, s)$$$
• For pair $$$(p, q)$$$
• • We would perform the operation on indices $$$[p, p + 1, p + 2, ..., q - 1]$$$. $$$(q - p)$$$ Operations.
• For pair $$$(r, s)$$$
• • We would perform the operation on indices $$$[r, r + 1, r + 2, ..., s - 1]$$$. $$$(s - r)$$$ Operations.

Now we just need to check if $$$(s - r) + (q - p) ≤ k$$$.

How do I solve this?

• Store a prefix sum for $$$+1$$$ and $$$-1$$$ occurences individually, this would help us find out their frequency in a range in $$$O(1)$$$ time. $$$O(n)$$$ processing though.
• Have two different std::vector<int>, storing the indices of $$$+1$$$ and $$$-1$$$ occurences. Can be done in $$$O(n)$$$ aswell.
• Have a $$$dp[n][2]$$$ for both of the std::vector's.

$$$dp[i][0]$$$: total cost of operations involving indices $$$i, i + 1, ..., n - 1$$$, without considering the pair $$$(i, i + 1)$$$.
$$$dp[i][1]$$$: total cost of operations involving indices $$$i, i + 1, ..., n - 1$$$, considering the pair $$$(i, i + 1)$$$.

$$$dp[i][0]$$$ is nothing but $$$dp[i + 1][1]$$$.
$$$dp[i][1] = v[i + 1] - v[i] + dp[i + 1][0]$$$.

Base Cases:
$$$dp[n - 1][0] = 0. dp[n - 1][1] = 0;$$$
$$$dp[n - 2][0] = 0. dp[n - 2][1] = v[n - 1] - v[n - 2].$$$

Computing this also takes $$$O(n)$$$.

For a query,

• $$$O(1)$$$: Find the number of $$$+1$$$'s or $$$-1$$$'s in $$$[L, R]$$$.
  
• $$$O(logn)$$$: In case either of them have an even count, find the left and ritemost indices using binary search over the vectors.
  
• $$$O(1)$$$: prefix sum on respective $$$dp$$$ using the positions of the bounded values found in step above.

Overall compleixity is $$$O(n + qlogn)$$$.