For any index $$$i$$$, it is always possible to make $$$a_i = b_i$$$ in at most $$$2$$$ moves.

Now there are four possible cases for a fixed index $$$i$$$.

1) If $$$a_i = b_i$$$, then no operation is required.

2) If $$$a_i \bmod b_i = 0$$$, then we can multiply $$$b_i$$$ by $$$\frac{a_i}{b_i}$$$, and make $$$a_i$$$ and $$$b_i$$$ equal using one operation.

3) If $$$b_i \bmod a_i = 0$$$, then we can multiply $$$a_i$$$ by $$$\frac{b_i}{a_i}$$$, and make $$$a_i$$$ and $$$b_i$$$ equal using one operation.

4) Otherwise, we can multiply $$$a_i$$$ by $$$b_i$$$ and $$$b_i$$$ by $$$a_i$$$, making them equal in two operations.

The answer is obtained by summing the minimum number of operations required for all indices $$$i$$$ from $$$1$$$ to $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<ll> a(n),b(n);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        for(int i=0;i<n;i++)
        {
            cin>>b[i];
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]==b[i])
            {

            }
            else if(a[i]%b[i]==0 || b[i]%a[i]==0)
            ans+=1;
            else
            ans+=2;
        }
        cout<<ans<<endl;
    }
}

Instead of trying to settle the given debts, calculate for each person their net debt to the rest of the group. Settling these net debts is equivalent to settling the given debts.

In each transaction, try to settle the debts for one person. after the $$$n-1^{th}$$$ transaction, the last person's debt will automatically be settled

For each person $$$i$$$, Calculate $$$bal[i] = \sum(\text{debts owed to person } i) — \sum(\text{debts owed by person} i)$$$ to be the net amount they are owed by the rest of the group (negative if they owe money to the rest of the group)

Now we will perform $$$n-1$$$ transactions. In the $$$i^{th}$$$ transaction, we will settle person $$$i$$$'s debt to the group by passing it on to the next person. To do this, Send $$$|bal[i]|$$$ money from person $$$i+1$$$ to $$$i$$$ if $$$bal[i] \gt 0$$$, or from person $$$i$$$ to person $$$i+1$$$ if $$$bal[i] \lt 0$$$ (If $$$bal[i] = 0$$$ this transaction can be skipped). Now person $$$i$$$'s net debt is settled and person $$$i+1$$$'s new balance is $$$bal[i]+bal[i+1]$$$

After the last transaction, the first $$$n-1$$$ people will have their debts settled by design. The last person's balance will the sum of all initial balances, which must sum to 0. Hence all debts have been settled.

n, M = map(int, input().split()) 
balance = [0] * (n)

for _ in range(M):
    a, b, x = map(int, input().split()) 
    balance[a-1] -= x
    balance[b-1] += x

transactions = []

# Perform n-1 transaction passing on the debt to the next person
for i in range(n-1):
    if balance[i]>0:
        transactions.append(f"{i+2} {i+1} {balance[i]}")
    elif balance[i]<0:
        transactions.append(f"{i+1} {i+2} {-balance[i]}")
    else:
        pass
    
    balance[i+1] += balance[i]

# Final person's debt will automatically be settled.
assert balance[-1] == 0

print(len(transactions))
print("\n".join(transactions))

Let $$$K$$$ be the total number of '1's in the entire tree after assigning all question marks. If an edge splits the tree into component $$${c}$$$ (say, child) and component $$${r}$$$ (say, root), try to rewrite the equilibrium condition ($$$0_{c} = 1_{r}$$$) in terms of component size $$$S_{c}$$$ and total ones $$$K$$$.

Notice that the structure of the tree (and thus the sizes of all subtrees) is fixed and never changes. However, the total number of '1's ($$$K$$$) is flexible depending on how many ? we turn into 1s.

Solution

Let $$$S_{c}$$$ be the size of component $$${c}$$$. Let $$$0_{c}$$$ and $$$1_{c}$$$ be the number of zeros and ones in component $$${c}$$$. Let $$$K$$$ be the total number of ones in the tree ($$$K = 1_{c} + 1_{r}$$$).

The problem requires $$$0_{c} = 1_{r}$$$. Since $$$S_{c} = 0_{c} + 1_{c}$$$, we can substitute $$$0_{c} = S_{c} - 1_{c}$$$. Since $$$K = 1_{c} + 1_{r}$$$, we can substitute $$$1_{r} = K - 1_{c}$$$.

Equating them:

Conclusion: An edge is valid if and only if the size of the subtree it cuts off is exactly equal to the total number of '1's in the entire tree.

Since we can choose how many ? become 1, the total $$$K$$$ can be any integer in the range:

Algorithm:

1. Run a DFS (or iterative traversal) to calculate the size of the subtree rooted at every node.

2. Store the frequency of each subtree size in an array cnt.

3. Iterate $$$K$$$ through the valid range $$$[min_{ones}, max_{ones}]$$$. The answer is the maximum value of cnt[K] found in this range.

Time Complexity: $$$O(N)$$$

Space Complexity: $$$O(N)$$$

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

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

    int min_k = 0, questions = 0;
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        if(s == "1") min_k++;
        if(s == "?") questions++;
    }

    vector<vector<int>> adj(n + 1);
    for(int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> subtree_size(n + 1, 0);
    vector<int> freq(n + 1, 0);

    auto dfs = [&](auto&& self, int u, int p) -> void {
        subtree_size[u] = 1;
        for(int v : adj[u]) {
            if(v != p) {
                self(self, v, u);
                subtree_size[u] += subtree_size[v];
            }
        }
        if(u != 1) {
            freq[subtree_size[u]]++;
        }
    };

    dfs(dfs, 1, 0);

    int ans = 0;
    int max_k = min_k + questions;
    int limit = min(n - 1, max_k);

    for(int k = min_k; k <= limit; k++) {
        ans = max(ans, freq[k]);
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) solve();
}

For a fixed index $$$l$$$, we try to count the number of subarrays starting at $$$l$$$ whose $$$mex = k$$$.

Let $$$r_1$$$ be the smallest index such that

Let $$$r_2$$$ be the smallest index such that

Here, $$$(l, r)$$$ denotes the subarray starting at index $$$l$$$ and ending at index $$$r$$$.

Then, the number of required subarrays starting at index $$$l$$$ is $$$r_2 - r_1$$$. We need to compute this value for all $$$l$$$ from $$$1$$$ to $$$n$$$.

Let $$$r_{l,1}$$$ denote the value of $$$r_1$$$ for a fixed index $$$l$$$, and let $$$r_{l,2}$$$ denote the value of $$$r_2$$$ for the same index.

It can be easily observed that

Thus, as $$$l$$$ increases, both $$$r_1$$$ and $$$r_2$$$ are non-decreasing. Using two pointers, the total number of queries needed is $$$4n$$$.

//Author : Praneeth Kodavati (CF - 0ne8)

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

void query(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    cout.flush();
}

void solve(){
    ll n,k;
    cin>>n>>k;
    ll r1=1,r2=1;
    ll mex;
    ll ans=0;
    for(ll i = 1 ; i <= n ; i++){
        r1=max(r1,i);
        query(i,r1);
        cin>>mex;
        bool flag=0;

        while(r1 <= n && mex < k){
            r1++;
            if(r1==n+1){
                flag=1;
                break;
            }
            query(i,r1);
            cin>>mex;
        }

        if(flag) break;
        r2=max(r2,r1);

        if(r2==n+1){
            ans+= r2-r1;
            continue;
        }

        query(i,r2);
        cin>>mex;
        while(r2 <= n && mex < k+1){
            r2++;
            if(r2==n+1) break;
            query(i,r2);
            cin>>mex;
        }

        ans += (r2-r1);
    }
    cout<<"! "<<ans<<endl;
    cout.flush();
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

The order of moves does not matter. Only the set of vertices that get claimed matters. In a tree, from any subtree you can either return to its root or end your walk inside it.

Since the graph is a tree, the path between any two vertices is unique. This strongly restricts the structure of any valid walk.

We start from the vertex $$$s$$$. Whenever we enter the subtree of a vertex, there are only two possibilities:

1) We fully explore this subtree and return to its root. 2) We end the journey somewhere inside this subtree and do not return.

There is no third option, because to visit vertices from different subtrees we must pass through their common ancestor.

As a consequence: - In every subtree, at most one branch can be used to end the journey. - All other chosen branches must be fully explored and returned from. - The claimed vertices always form a connected subtree containing $$$s$$$.

Let $$$T$$$ be the connected subtree of claimed vertices containing $$$s$$$.

Every edge in $$$T$$$ is traversed twice, except the edges on the path from $$$s$$$ to the final vertex, which are traversed only once. Hence, the total distance traveled is:

From the subtree $$$T$$$: - We gain $$$\text{val}[v]$$$ for every vertex $$$v \in T$$$. - We pay twice the weight of every edge. - We save the distance of the final path.

Thus, the total score equals:

We root the tree at $$$s$$$ and use dynamic programming.

Define: - $$$A[u]$$$: maximum score if we claim vertices in the subtree of $$$u$$$ and return to $$$u$$$. - $$$AD[u]$$$: maximum score if the journey may end anywhere in the subtree of $$$u$$$.

For a child $$$v$$$ of $$$u$$$ with edge weight $$$w$$$: - Returning from $$$v$$$ contributes $$$\max(0, A[v] - 2w)$$$. - Ending inside $$$v$$$ contributes $$$AD[v] - w$$$.

At each vertex $$$u$$$, we take all profitable return contributions and choose at most one subtree where the journey ends.

The final answer is $$$AD[s]$$$.

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

using ll = long long;

void solve(){

    int n;
    cin >> n;

    vector<ll> val(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    vector<vector<pair<int,ll>>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int s;
    cin >> s;

    /* Build parent array and traversal order */
    vector<int> parent(n + 1, -1);
    vector<ll> par_w(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    stack<int> st;
    st.push(s);
    parent[s] = s;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (auto [v, w] : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                par_w[v] = w;
                st.push(v);
            }
        }
    }

    /* DP arrays */
    vector<ll> A(n + 1, 0), AD(n + 1, 0);

    /* Process nodes in postorder */
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        ll sum_add = 0;
        ll best_extra = 0;

        for (auto [v, w] : adj[u]) {
            if (parent[v] != u) continue;

            ll add = max(0LL, A[v] - 2 * w);
            sum_add += add;

            ll deep = AD[v] - w;
            best_extra = max(best_extra, deep - add);
        }

        A[u] = val[u] + sum_add;
        AD[u] = A[u] + max(0LL, best_extra);
    }

    cout << AD[s] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
        solve();
}

Each edge is either present in one face or in two faces.

The summation of the number of faces each vertex is present in is equal to $$$\sum$$$ number of faces each edge is present in.

$$$\sum$$$ edges(number of faces) = $$$\sum$$$ faces(number of edges).

For any face, the number of edges on its boundary is equal to the number of vertices on its boundary. Hence, $$$\sum$$$ faces(number of edges) = $$$\sum$$$ faces(number of vertices) = $$$\sum$$$ vertices(number of faces).

We need to find the number of edges present in two faces, which is simply $$$\sum$$$ (number of faces each edge is present in) — m. Instead, applying Hint 2, we compute the number of faces each vertex is present in.

Using Tarjan’s algorithm, we first remove all the bridges, which decomposes the graph into biconnected components (BCCs). Then, for a vertex, the number of faces it is present in is equal to its degree minus the number of connected components formed after removing that vertex.

Therefore, the final answer is $$$\sum_{v=1}^{n}$$$ (deg(v) — number of connected components formed after removing v) — m, computed after the removal of bridges.

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

const int MAXN = 2e5 + 15;
vector<int> adj[MAXN], dadj[MAXN]; 
int disc[MAXN], low[MAXN], timer = 0;
bool is_articulation[MAXN];
vector<int> st;
vector<vector<int>> bccs;

vector<bool> visited;
vector<int> tin;
map<pair<ll,ll>,ll> vv;

void bdfs(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
bool parent_skipped = false;
for (int to : dadj[v]) {
    if (to == p && !parent_skipped) {
    parent_skipped = true; continue; }
    if (visited[to]) {
    low[v] = min(low[v], tin[to]);
    } else {
    bdfs(to, v);
    low[v] = min(low[v], low[to]);
    if (low[to] > tin[v]) {
        vv[{v, to}] = 1; vv[{to, v}] = 1;
    }
    }
}
}
void find_bridges(int n) {
timer = 0;
visited.assign(n, false); tin.assign(n, false);
for (int i = 0; i < n; ++i) if (!visited[i]) bdfs(i);
}

void find_bccs(int u, int p = -1) {
    disc[u] = low[u] = ++timer;
    st.push_back(u);
    int children = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (disc[v]) {
            low[u] = min(low[u], disc[v]);
        } else {
            children++;
            find_bccs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) {
                is_articulation[u] = (p != -1 || children > 1);
                vector<int> component;
                while (true) {
                    int node = st.back();
                    st.pop_back();
                    component.push_back(node);
                    if (node == v) break;
                }
                component.push_back(u);
                bccs.push_back(component);
}}}}

void solve(){
    ll n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        dadj[x].push_back(y);
        dadj[y].push_back(x);
    }

    find_bridges(n);
    ll br = 0;
    for(int i = 0; i < n; i++) {
        for(auto &x : dadj[i]) {
            if(vv[{x, i}]){
                br++;
                continue;
            } 

            adj[i].push_back(x);
        }
    }
    br /= 2;
    ll cnt = 0;
    for(int i = 0; i < n; i++) {
        if(!disc[i]){
            find_bccs(i, -1);
            cnt++;
        }
    }

    ll sz = bccs.size();
    ll ans = m - n - sz + cnt - br;

    cout << ans << endl;

    for(int i = 0; i < n; i++) {
        dadj[i].clear();
        adj[i].clear();
        low[i] = 0;
        disc[i] = 0;
    }
    timer = 0;
    bccs.clear();
    st.clear();
    vv.clear();
    tin.clear();
    visited.clear();
}

int main(){ 
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin>>t;
    while(t--)
    solve();
}

We are given an unknown integer $$$x$$$ such that $$$1 \le x \le 10^8$$$. The goal is to determine the value of $$$x$$$ using interactive queries.

If we know the value of $$$x \bmod p_i$$$ for several primes $$$p_i$$$, then the value of

is uniquely determined.

If

then $$$x \bmod \prod p_i = x$$$, since $$$1 \le x \le 10^8$$$. Hence, the value of $$$x$$$ itself is uniquely determined.

Therefore, we choose primes such that their product is greater than $$$10^8$$$. In this solution, we use the primes $$$101, 103, 107,$$$ and $$$109$$$.

Now, the remaining task is to compute $$$x \bmod p$$$ for each chosen prime $$$p$$$.

Fix a prime $$$p$$$.

First, we query

If $$$x \equiv 0 \pmod p$$$, then $$$L_1$$$ is divisible by $$$p$$$. Otherwise,

Next, we query

If $$$x \equiv p-2 \pmod p$$$, then $$$L_2$$$ is divisible by $$$p$$$. Otherwise,

In the non-divisible case, subtracting the two expressions gives

From this, we can compute

where $$$inv(4)$$$ denotes the modular inverse of $$$4$$$ modulo $$$p$$$.

Thus, we can determine $$$x \bmod p$$$ using atmost two queries for each prime.

After computing the remainders of $$$x$$$ modulo $$$101, 103, 107,$$$ and $$$109$$$, we combine them to obtain $$$x \bmod \prod p_i$$$.

Since the product of these primes is greater than $$$10^8$$$, this value is equal to $$$x$$$ itself.

Hence, the value of $$$x$$$ is uniquely determined.

The total number of queries used is atmost $$$8$$$.

//uthor - Praneeth Kodavati 

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define vec vector
#define pll pair<ll,ll>

ll binpow(ll a,ll b,ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

long long modinv(long long a, long long m) {
    return binpow(a, m - 2, m);
}


void query(ll l,ll r){
    cout<<"? "<<l<<" "<<r<<endl;
    cout.flush();
}

void solve(){
    ll MOD = 1;
    vec<ll> primes = {101,103,107,109};
    vec<ll> rem(150);
    ll val1,val2;
    for(auto p : primes){
        MOD *= p;
        query(0,p);
        cin>>val1;
        if(val1%p==0){
            rem[p]=0;
            continue;
        }
        query(2,p+2);
        cin>>val2;
        if(val2%p==0){
            rem[p]=p-2;
            continue;
        }
        val1 %= p;
        val2 %= p;
        rem[p] = (val2-val1-4+4*p)*modinv(4,p);
        rem[p] = (rem[p]+p)%p;
    }

    ll cur = rem[101] ;
    ll mod = primes[0];

    for(int i = 1 ; i < 4 ; i++){
        ll p = primes[i];
        long long k = 0;
        while ((cur + k * mod) % p != rem[p]) k++;
        cur = cur + k * mod;
        mod *= p;
    }

    cout<<"! "<<cur%MOD<<endl;
    cout.flush();
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}