I submitted a solution for E but I can't prove it's time complexity, and I'm 85% sure it shouldn't pass. Please hack it and provide me the case.

The idea is: The cost of any node is either sum of costs of its children or sum of costs of its children + 1, so we want to save that extra 1. For every node, store the gcd of any path that guarantees minimum cost as gcd[u]. now, for every node, start a bfs to children, and keep the gcd of the each current path you've taken, until the gcd(current path, gcd[u]) != 1, hence we can connect those two paths to save that extra 1 and we can stop the search. If the gcd(current path, arr[u]) = 1, that means we can't benefit anything from that node and we have to consider that visited node as a different path which doesn't save us the extra 1. If instead gcd(current path, arr[u]) != 1, we continue the search.

Here's the code:

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

#define pb push_back
#define ll long long
#define endl '\n'

void solve(){

    int n;
    cin >> n;
    vector<ll> arr(n + 1), gcd(n + 1);
    vector<vector<int>> g(n + 1, vector<int> ());
    vector<int> dp(n + 1);
    
    for(int v = n; v >= 1; v--){
        int k;
        cin >> arr[v] >> k;
        dp[v] = 1;
        gcd[v] = arr[v];
        queue<pair<int, ll>> q;
        for(int i = 0; i < k; i++){
            int u;
            cin >> u;
            q.push({u, arr[v]});
            g[v].pb(u);
            dp[v] += dp[u];
        }   
        while(q.size()){
            auto [u, curr] = q.front();
            q.pop();
            if(__gcd(curr, gcd[u]) != 1LL){
                dp[v]--;
                gcd[v] = __gcd(curr, gcd[u]);
                break;
            }
            if(__gcd(curr, arr[u]) != 1LL){
                for(int j : g[u]){
                    q.push({j, __gcd(curr, arr[u])});
                }
            }
        }


        cout << dp[v] << endl;
        cout.flush();
    }

}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;

    while(t--)
        solve();

    return 0;
}

The idea also appeared in a previous div1.B

we want a[i] * a[j] = j — i

let's make an assumption, a[i] & a[j] are both larger than sqrt(j — i), then, a[i] * a[j] would be larger than j — i. Hence our assumption is wrong, and the opposite of our claim is true, i.e. either a[i] <= sqrt(j — i) or a[j] <= sqrt(j — i). (If you know DeMorgan's law it'll be clear how we inverted the statement).

by the previous statement, we can pair an element <= sqrt(n) with an element <= sqrt(n). And, we can also pair an element <= sqrt(n) with an element >= sqrt(n). These two scenarios are allowed, but we can't pair two elements >= sqrt(n).

iterate through the elements and call the current element x.

if x >= sqrt(n): we need an element y with a distance d from the current element such that x * y = d. From the equation we see that d is a multiple of x. Hence, x <= d = x * y <= n — 1 (the farthest pair possible)

rewriting, x <= x * y <= (n — 1) / x --> 1 <= y <= (n — 1) / x, we said that x >= sqrt(n), that means the worst case for the value of y is sqrt(n) (plugging the smallest value of x = sqrt(n) to make (n — 1) / x as large as possible).

You can iterate through the possible values of y, setting d = x * y, and checking if the element behind the current element by d equals y, or the element in front of you by d equals y.

If x <= sqrt(n): we want to pair it with an element <= sqrt(n), and not with an element >= sqrt(n) since in the previous part we did that already.

since we want to pair it with an element <= sqrt(n), we can just brute force this value (call it y). 1 <= y <= sqrt(n). We want an element that equals y with a distance x * y from the current element, rather than checking the indices of y in the array, we can instead use the info that d = x * y and check the element behind me by d and in front of me by d and seeing if it equals y or not. (you need to handle the collisions btw)

I've commented an another solution below you maybe it'll make sense. Hope that helped :>

Another solution for B div1:

let d be the the distance j — i (d = j — i), x = a[i], y = a[i].

x * y = d.

let x = min(x, y), y = max(x, y).

we know that x <= sqrt(d) and y >= sqrt(d) ==> y ^ 2 >= d.

we also know that d % y = 0, i.e. d = c * y where c is some constant. Hence, y <= d.

since d is the difference of the indices, it's max value is n — 1, we can write it as d <= n for the sake of simplicity.

y <= d <= min(n, y ^ 2), but d = c * y

y <= c * y <= min(n, y ^ 2), dividing by y we get

1 <= c <= min(n / y, y), that worst case for min(n / y, y) is y = sqrt(n). Hence, 1 <= c <= sqrt(n).

we can iterate through the elements of the array supposing the current element is the max between the elements in the pair (i.e. y in the explanation), and brute forcing the value of c to get every possible value of d as d = c * y.

void solve(){

    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        int y = arr[i];
        if(arr[i] >= n)
            continue;
        
        int lim = min(n / y, y);
        for(int c = 1; c <= lim; c++){
            int d = c * y;
            if(i + d < n && arr[i + d] * y == d)
                ans++;
            if(i - d >= 0 && arr[i - d] * y == d && arr[i - d] != y)
                ans++;
        }
    }

    cout << ans << endl;

}

my O(n) solution for E (it's possible to get rid of the deque and the pair but I'm just lazy):

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

#define pb push_back
#define ll long long
#define endl '\n'

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> arr(n), freq(3 * n + 1, 0);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        freq[arr[i]]++;
    }
    
    int ans = 0, last = 0;
    deque<pair<int, int>> dq;
    function <void (int)> func = [&](int x){
        if(x > k){
            dq.push_front({x - 1, last * dq.empty()});
        }else if(dq.size()){
            dq[0].first += x - 1;
        }
    };

    for(int i = 1; i <= 3 * n; i++){
        if(freq[i] == 0 && dq.size()){
            if(dq.size() == 1)
                last = dq[0].second;
            freq[i] = dq[0].first;
            dq.pop_front();
        }

        func(freq[i]);
        if(dq.size())
            ans = max(ans, ++dq.back().second);
        else
            last = 0;
    }

    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;

    while(t--)
        solve();

    return 0;
}

ACCEPTED!!!

dw bro he's my friend we're just joking

you can't even do simple math?

you are true , it was very clear.

TY for the contest <3

GET GOOD!!

RACIST

but why doesn't it exceed 1e7?

Thanks bro <3