In the following question, The Rook can attack the king if the Rook and the King are on the same vertical or horizontal line. It is only possible when $$$a$$$ and $$$x$$$ are the same or $$$b$$$ and $$$y$$$ are the same.

#include <bits/stdc++.h>
using namespace std;
 
int main ()
{
  int testcase;
  cin >> testcase;
 
  while (testcase--){
      
      int a,b,x,y;
      
      cin>>a>>b;
      cin>>x>>y;
      
      if(x == a || y == b){
          cout<<"YES"<<endl;
      }
      
      else{
          cout<<"NO"<<endl;
      }
  }
}

Since we have to delete a single element from the array(let that element have index $$$ind$$$), so the main thing that we need to focus is that the elements with index $$$>$$$ $$$ind$$$, will have a change in the parity of their indexes, i.e., the elements present at odd indices initially will get moved to the even index and vice versa. So, for every index $$$ind$$$, we have to check whether the sum of all elements at the odd indices($$$i$$$) such that $$$i < ind$$$ and with even indices($$$j$$$) such that $$$j > ind$$$ (since they would have moved to odd indices after the deletion) and equate the sum to the sum of all elements at the even indices($$$i$$$) such that $$$i < ind$$$ and with odd indices($$$j$$$) such that $$$j > ind$$$.

Now, to calculate the sums of respective odd and even indices till index $$$ind$$$, we will use an specialized version of prefix sum which stores the prefix sum of only even indexes or only odd indexes, and to calculate the sum of those after index $$$ind$$$, we will similarly calculate specialized suffix sum for both odd and even trailing indices.

So, while checking if we can remove the number at index `ind' or not, we can check whether $$$preeven[ind-1]+sufodd[ind+1]=preodd[ind-1]+sufeven[ind+1]$$$.

#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);

void solve()
{
    int n;
    cin>>n;
    vector<long long int>arr(n);
    for(auto &x:arr)cin>>x,assert(x>=1 && x<=1000000000);
    vector<long long int>preodd(n,0),preeven(n,0),sufodd(n,0),sufeven(n,0);
    preeven[0]=arr[0];
    if(n==1)
    {
        cout<<"1"<<endl;return;
    }
    for(int i=1;i<n;i++)
    {
        if(i%2)
        {
            preodd[i]=arr[i]+preodd[i-1];
            preeven[i]=preeven[i-1];
        }
        else{
            preodd[i]=preodd[i-1];
            preeven[i]=arr[i]+preeven[i-1];
        }
    }
    if((n-1)%2)sufodd[n-1]=arr[n-1];
    else sufeven[n-1]=arr[n-1];
    for(int i=n-2;i>=0;i--)
    {
        if(i%2)
        {
            sufodd[i]=arr[i]+sufodd[i+1];
            sufeven[i]=sufeven[i+1];
        }
        else{
            sufodd[i]=sufodd[i+1];
            sufeven[i]=arr[i]+sufeven[i+1];
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(i==0)
        {
            cnt+=(sufeven[1]==sufodd[1]);
        }
        else if(i==n-1)
        {
            cnt+=(preodd[n-2]==preeven[n-2]);
        }
        else{
            if(preeven[i-1]+sufodd[i+1]==preodd[i-1]+sufeven[i+1])cnt++;
        }
    }
    cout<<cnt<<endl;
}
signed main() {
    speed
 
   int t=1;
   cin>>t;
   assert(t>=1 && t<=10000);
   while(t--)
   {
      solve();
   }
   return 0;
}

We can use a stack data structure to solve the problem. For any index $$$i \ge 2$$$, we will pop the previous two characters and check whether the previous two characters and the current character can make a "BIT" string. If they can't make a "BIT" string, then we will push them again in their previous order, followed by the character of the current index.

#include <bits/stdc++.h>
using namespace std;
    
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    stack<char> st;
    st.push(s[0]);
    st.push(s[1]);
    for(int i=2;i<n;i++) {
        if(st.size()>=2) {
            char x=st.top();
            st.pop();
            char y=st.top();
            st.pop();
            string tmp;
            tmp+=y;
            tmp+=x;
            tmp+=s[i];
            if(tmp!="BIT") {
                st.push(y);
                st.push(x);
                st.push(s[i]);
            } 
        }
        else {
            st.push(s[i]);
        }
    }
    string ans="";
    int sz=st.size();
    for(int i=0;i<sz;i++) {
        ans+=st.top();
        st.pop();
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<'\n';
}
    
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    cin >> t;
    for (int T = 1; T <= t; T++) {
        // cout << "Case #" << T << ": ";
        solve();
    }
    return 0;
}

Here we can have use prefix sum to find size of any of three branch individually. We will make three array denoting size of that branch for every point(refer solution for clarification). Then we will take max size of $$$Y$$$ at any point by taking minimum of any all $$$3$$$ branches. We know that we can obtain any lower sized $$$Y$$$, if we can obtain higher sized $$$Y$$$. So we will take suffix sum of final array.

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

int main(){
    int tc;
    cin>>tc;
    while(tc--){
        int n;
        cin>>n;
        string str[n];
        for(int i=0;i<n;i++){
            cin>>str[i];
        }
        int upLeft[n][n],upRight[n][n],down[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                upLeft[i][j]=0;
                upRight[i][j]=0;
                down[i][j]=0;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                if(str[i-1][j-1]=='#' && str[i][j]=='#'){
                    upLeft[i][j]=1+upLeft[i-1][j-1];
                }
            }
        }
        for(int i=1;i<n;i++){
            for(int j=n-2;j>=0;j--){
                if(str[i-1][j+1]=='#' && str[i][j]=='#'){
                    upRight[i][j]=1+upRight[i-1][j+1];
                }
            }
        }
        for(int i=n-2;i>=0;i--){
            for(int j=0;j<n;j++){
                if(str[i+1][j]=='#' && str[i][j]=='#'){
                    down[i][j]=1+down[i+1][j];
                }
            }
        }
        vector<int> ans(n+1,0);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans[(min({upLeft[i][j],upRight[i][j],down[i][j]}))]++;
            }
        }
        for(int j=n-1;j>=0;j--){
            ans[j]+=ans[j+1];
        }
        for(int i=1;i<n+1;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
}

It's obvious that if the destination cell is reachable from the start cell without the help of a magic spell, then the answer is $$$0$$$.

Otherwise,

We will store all reachable cells value from the start cell $$$(r_s,c_s)$$$ in a vector named arr1 using simple BFS or DFS, then we will store all reachable cells value from destination cells $$$(r_d,c_d)$$$ in another vector named arr2 using simple BFS or DFS.

Now our problem is that you have given two arrays and found an element such that its absolute sum is minimized. which can easily be done using the binary search or two-pointer method.

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

#define int long long
#define all(a) (a).begin(), (a).end()

vector<vector<int>> v(1005, vector<int>(1005, 0));
int visited[1005][1005];

bool solve(int x, int y, int n)
{
    if (x <= 0 || x > n || y <= 0 || y > n)
        return 0;
    if (visited[x][y])
        return 0;
    if (v[x][y] == 0)
        return 0;
    return 1;
}

void solve(int r, int c, vector<int> &as, int n)
{
    memset(visited, 0, sizeof(visited));

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = 1;
    as.push_back(v[r][c]);
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = p.first + dx[i];
            int y = p.second + dy[i];
            if (solve(x, y, n))
            {
                visited[x][y] = 1;
                as.push_back(v[x][y]);
                q.push({x, y});
            }
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> v[i][j];
        }
    }

    vector<int> arr1, arr2;

    solve(r1, c1, arr1, n);
    if (visited[r2][c2])
    {
        cout << 0 << endl;
        return;
    }
    
    arr2.push_back(-1e18);
    solve(r2, c2, arr2, n);
    arr2.push_back(1e18);
    sort(arr2.begin(), arr2.end());

    int ans = 1e18;
    
    for (int i = 0; i < arr1.size(); i++)
    {
        int val = arr1[i];
        int ind = lower_bound(arr2.begin(), arr2.end(), -val) - arr2.begin();
        ans = min(ans, abs(val + arr2[ind]));
        if (ind)
            ans = min(ans, abs(val + arr2[ind - 1]));
    }
    cout << ans << endl;
}

signed main()
{   
    int t=1;
    // cin>>t;
    while(t--) {
        solve();
    }
}

In this question, you can count contribution of any edge in score of any player by rooting on it. So here we can find difference between contribution. So now we have got answer without changing any edge.

You have to observe that by doing any edge $$$0$$$, we are subtracting contribution of that edge to the answer, and by doing any edge $$$2$$$ we are adding contribution of that edge to the answer. So we will store all contributions as absolute value as we can decrease it if it is negative(in order to make positive impact on answer). We will take maximum impact edge first, and by doing this we can find answer.

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

const int N=5e5+5;
vector<int> edge[N];
int sz[N];
int ans=0;
map<pair<int,int>,int> edgeUseDiff;
void dfs(int ind,int par,int chk){
    sz[ind]=1;
    for(auto chld:edge[ind]){
        if(par==chld)continue;
        dfs(chld,ind,chk);
        sz[ind]+=sz[chld];
        edgeUseDiff[{min(ind,chld),max(ind,chld)}]+=((chk?1:-1)*sz[chld]);
        ans+=((chk?1:-1)*sz[chld]);
    }
}

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(a,-1,1);
    dfs(b,-1,0);
    vector<int> vc;
    for(auto it:edgeUseDiff){
        vc.push_back(abs(it.second));
    }
    sort(vc.begin(),vc.end());
    reverse(vc.begin(),vc.end());
    cout<<ans<<" ";
    for(int i=0;i<n-1;i++){
        ans+=vc[i];
        cout<<ans<<" ";
    }
    cout<<endl;
    return 0;
}