It is always difficult to deal with $$$gcd = 1$$$. Think about the same problem with $$$gcd(c_u,c_v)>1$$$.

To solve the original problem, just count the total number of paths contain the $$$i^{th}$$$ edge, and subtract the result from Hint1.

Still hard to deal with $$$gcd(c_u,c_v)>1$$$, try to solve it for $$$gcd(c_u,c_v)=x$$$ $$$(x > 1)$$$

You can solve Hint3 through Inclusion-Exclusion Principle or Mobius Function. With the help of some tree techniques like Centroid, Sack or Auxiliary Tree.

Full tutorial will be published soon.

Try to solve the problem in a brute force approach.

Instead of inserting an integer $$$x$$$ $$$(|x| = k)$$$ in any position $$$p$$$ $$$(1 \le p \le n)$$$ and finding the maximum xor. (which has a complexity $$$O(n^3 \times C(10,k)$$$ where $$$C(10,k)$$$ is the number of way to choose $$$k$$$ bits from $$$10$$$ bits.)

You can think of a better way, find the xor of a subarray $$$a[l;r]$$$ and try all possible values $$$x$$$, then take the maximum among them (which has a complexity $$$O(n^2 \times C(10,k)$$$)

Let $$$pref_0 = 0$$$ , $$$pref_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$$ $$$(1 \le \ i \le n)$$$.

To calculate $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_r$$$ we can use the previous precalculated array. $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_r = pref_r \oplus pref_{l-1}$$$ .

We only interest about the distinct values among $$$pref_r \oplus pref_{l-1}$$$ where $$$(1 \le l \le r \le n)$$$

Let $$$pref_0 = 0$$$ , $$$pref_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$$ $$$(1 \le \ i \le n)$$$.

Number of distinct values among $$$pref_r \oplus pref_{l-1}$$$ where $$$(1 \le l \le r \le n)$$$ is less than or equal $$$2^{10}$$$. (You can find these values with complexity $$$O(2^{2\times 10})$$$).

After finding these values, try all possible integers $$$x$$$ $$$(|x| = k)$$$.

Time complexity will be $$$O(2^{20})$$$ per each test.

/*
    Enjoy the journey
*/
#include <bits/stdc++.h>
using namespace std;

int NUMTESTCASE;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
    for (cin >> NUMTESTCASE ; NUMTESTCASE ; NUMTESTCASE --) {
        vector <bool> Pref (1 << 10) ;
        vector <bool> Sub (1 << 10) ;
        int n , k , x , PrefXor = 0 ;
        cin >> n >> k ;
        Pref [0] = true ;
        for (int i = 1 ; i <= n ; i ++) {
            cin >> x ;
            PrefXor ^= x ;
            Pref [PrefXor] = true ;
        }
        for (int x = 0 ; x < (1 << 10) ; x ++)
            if (Pref [x])
                for (int y = 0 ; y < (1 << 10) ; y ++)
                    if (Pref [y])
                        Sub [x ^ y] = true ;

        int Ans = 0 ;
        for (int x = 0 ; x < (1 << 10) ; x ++)
            if (Sub [x]) {
                Ans = max (Ans , x) ;
                for (int y = 0 ; y < (1 << 10) ; y ++)
                    if (__builtin_popcount (y) == k)
                        Ans = max (Ans , x ^ y) ;
            }

        cout << Ans << '\n' ;
    }
    return 0;
}

let's consider for each string the minimum changes to make it palindrome as for example : the first test case = [1,2,2,2,1,1]

Try thinking of prefix sums furthermore sparse Table

It will be little bit hard to get the idea in this way but if you concern about prefix sums with the first array we made from the strings -- pre[0,1,3,5,7,8,9] (_return to hint1_) , we will only concern about sub-arrays [l:r] which has value which has value (pre[r]-pre[l]) <=k , then for each index we will find the index makes sub-array satisfying the above condition ,to make it clear let's consider subarray starting from index 2, it can take strings up to the 5th index (8-1<=7),and this can be easly get by binary search.

moving in to the second part we want to know the maximum value we can get ,in other words the index which I have to stop on it to get the maximum answer for this sub-array ,so we will also make prefix sum for the array of scores to get from it the maximum answer but how??!

let us also consider the first test case the the array will be scores[0,3,15,14,12,21,23] so the beginning from index 2 it will be optimal to stop at index 5 as it has the maximum value in the range , and this max range query can be done using sparse table ,so final answer will be (scores[max value index] — scores[i-1]).

solution by
algohary
ahmedtawfik

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;
   cin >> t;
   while (t--) {
      int n, k;
      cin >> n >> k;
      vector<string> a(n);
      vector<int> score(n);
      for (auto& i : a) cin >> i;
      for (auto& i : score) cin >> i;

      vector<int> b(n);
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < a[i].size() / 2; j++) {
            b[i] += (a[i][j] != a[i][a[i].size() - j - 1]);
         }
      }

      vector<ll> pref1(n + 1), pref2(n + 1);
      partial_sum(begin(b), end(b), begin(pref1) + 1);
      partial_sum(begin(score), end(score), begin(pref2) + 1);

      int LOG = __lg(n + 1) + 1;
      vector rmq(n + 1, vector(LOG, 0ll));
      for (int i = 0; i <= n; i++) rmq[i][0] = pref2[i];
      for (int j = 1; j < LOG; j++) {
         for (int i = 0; i + (1 << j) - 1 <= n; i++) {
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
         }
      }
      auto maxq = [&](int l, int r) {
         int k = __lg(r - l + 1);
         return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
      };


      // pref1[i] + k
      ll ans = -2e18;
      for (int i = 0; i <= n; i++) {
         auto it = upper_bound(begin(pref1) + i + 1, end(pref1), pref1[i] + k);
         --it;
         int R = it - begin(pref1);
         ans = max(ans, maxq(i, R) - pref2[i]);
         //cout << ans << " ";
      }
      //cout << "\n";
      cout << ans << "\n";

   }
   return 0;
}