Epiphany 13.0 A — Gifts

The minimum number of operations required to sort a list of $$$n$$$ gifts is $$$n−x$$$, where $$$x$$$ is the length of the longest sorted suffix.

Proof:

Let $$$k$$$ be the minimum number of steps required to sort the gifts. Observe that if $$$k$$$ steps are optimal, the first $$$k$$$ gifts must be moved, implying that the remaining $$$n-k$$$ gifts were already sorted in ascending order.

Consider the $$$n-k$$$ sorted gifts at the end. We can iteratively insert the unsorted gifts into this suffix to achieve complete sorting: Pick the first unsorted gift and place it in its correct position within the sorted suffix, maintaining the sorted order. Repeat this process for the remaining $$$k−1$$$ unsorted gifts. This takes $$$k$$$ operations.

#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
 
using namespace std;
 
void solve(){
    int n;
    cin>>n;
    vector<int> v(n);
    forn(0,n,i) cin>>v[i];
    int prev=v[n-1]+10;
    for(int i=n-1;i>=0;i--){
        if(v[i]>prev){
            cout<<i+1;
            return;
        }
        prev=v[i];
    }
    cout<<0;
}
 
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}

Epiphany 13.0 B — Hulk Smash

Observations

• The number of zeroes in the fully reconstructed sequence directly corresponds to the number of transformations.
• Each non-zero value $$$x$$$ in the sequence suggests that the $$$x$$$ entries immediately preceding this must be $$$x−1,x−2,…,0$$$. Fill in any missing values $$$(-1)$$$ with these corresponding values. The problem statement ensures the consistency of provided sequences.
• After filling some $$$(-1)$$$ as described in observation $$$2$$$, some $$$(-1)$$$ entries might remain. These can be filled in two ways:
  • Replace $$$(-1)$$$ with $$$0$$$, creating a potential transformation.
  • Replace $$$(-1)$$$ with $$$a_{i-1}+1$$$, continuing a previous streak.

• Previous observation implies that a range of zeroes can be achieved:

  • Maximum Zeroes: Fill all remaining $$$(-1)$$$ with $$$0$$$.
  • Minimum Zeroes: Fill all remaining $$$(-1)$$$ with preceding values, to continue streaks (as described above).

Let $$$minzero$$$ and $$$maxzero$$$ represent the minimum and maximum achievable zero counts. To answer a query $$$x$$$, check if $$$minzero ≤ x ≤ maxzero$$$.

If true, output $$$YES$$$, indicating a feasible sequence with $$$x$$$ transformations. strategy: let $$$k = x - minzero$$$ then for the first $$$k-1$$$ missing values which are remaining after applying observation $$$2$$$, fill them with $$$0$$$ and for the remaining continue the preceding streak, hence number of zeroes become $$$x$$$.

If false, output $$$NO$$$, indicating no such sequence exists.

#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
 
using namespace std;
 
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> v(n);
    forn(0,n,i) cin>>v[i];
    int prev=-1;
    v[0]=0;
    for(int i=n-1;i>0;i--){
        if(v[i]==-1){
            if(prev==-1) continue;
            else {
                v[i]=prev;
                prev--;
            }
        }
        else{
            prev=v[i]-1;
        }
    }
    int ans=0,extra=0;
    forn(0,n,i){
        if(v[i]==-1)extra++;
        else if(v[i]==0) ans++;
    }
    int left=ans,right=ans+extra;
    forn(0,q,i){
        int x;
        cin>>x;
        if(x>=left && x<=right) cout<<"YES\n";
        else cout<<"NO\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}

Epiphany 13.0 C — Fight Between Friends

Sort both the arrays in increasing order of the strengths.

Consider the strengths of an individual from Alice's team denoted by $$$x$$$, and the strengths of all individuals from Bob's team denoted by $$$b_1, b_2, ..., b_m$$$. If $$$b_k \le x$$$ and $$$b_{k+1} \gt x$$$, then the points gained by a person from Alice's team with strength $$$x$$$ will be $$$k$$$ and can be determined using the lower_bound($$$x$$$) function on the array $$$b$$$ (representing the strengths of Bob's team).

T.C: O((N + M) * (logN + logM))

Epiphany 13.0 C — Fight Between Friends

Sort both the arrays in increasing order of the strengths.

By iterating through each person from Alice's team, one person compares their strength with individuals from Bob's team. If the first person ($$$i=0$$$) from Alice's team can beat $$$j$$$ people, then in the next iteration ($$$i=1$$$, representing the next person from Alice's team), it assures that this person will beat $$$j$$$ people. In addition to this, the process continues to identify other individuals whom the person in the current iteration ($$$i=1$$$) can defeat to the persons from Bob's team.

T.C: O(N * logN + M * logM)

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

#define endl                                    "\n"
#define int                                     long long
#define all(a)                                  a.begin(), a.end()

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int j = 0; j < m; j++)
	{
		cin >> b[j];
	}
	sort(all(a));
	sort(all(b));
	function<int(vector<int>, vector<int>)> run = [&](vector<int> a, vector<int> b)
	{
		int ans = 0;
		for(int i = 0; i < a.size(); i++)
		{
			auto it = lower_bound(all(b), a[i]);
			if(it != b.begin())
			{
				if(it == b.end() || *it >= a[i]) it--;
				ans = (ans + (it - b.begin() + 1)) % mod;
			} 
		}
		return ans;
	};
        cout << run(a, b) << " " << run(b, a) << endl;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1; 
    while(t--)
    {
        solve();
    }
 
    return 0;
}

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

#define endl                                    "\n"
#define int                                     long long
#define all(a)                                  a.begin(), a.end()

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int j = 0; j < m; j++)
	{
		cin >> b[j];
	}
	sort(all(a));
	sort(all(b));
	function<int(vector<int>, vector<int>)> run = [&](vector<int> a, vector<int> b)
	{
		int ans = 0;
		int i = 0, j = 0;
		while(i < a.size())
		{
			while(j < b.size() && a[i] > b[j]) { j++; }
			ans = (ans + j) % mod;
			i++;
		}
		return ans;
	};
	cout << run(a, b) << " " << run(b, a) << endl;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1; 
    while(t--)
    {
        solve();
    }
 
    return 0;
}

Epiphany 13.0 D — SOS Signal

The given problem can be stated as an equation to find solution for linear equation

This equation is called a Diophantine equation. Let equation (1) be satisfied for some x and y then the time when the signal can be successfully read can be given as

Result 1: A solution to linear Diophantine equation $$$mx+ny=r$$$ exists only if $$$gcd(m,n) ∣ r$$$. If solution exists, let's say $$$(x_\circ,y_\circ)$$$ then there are infinite solutions, generalizing

Result 2: Using the Euclid Algorithm, a solution to the following equation can be obtained.

Rewriting our original equation we have,

Let $$$g=gcd(c,d)$$$ then if $$$g∤k$$$ then solution doesn't exist and we can print $$$-1$$$ as output.

If $$$g∣k$$$, then we need to find the solution for the equation $$$(2)$$$, such that both $$$(x, y)$$$ are the smallest positive pair (for the first time the ship reads signal successfully).

Let's say $$$(x_0,y_0)$$$ are solutions for the equation $$$(c/g)x+(d/g)y=1$$$ which can be obtained using Euclid's algorithm.

This implies that $$$(x′,y′)=(x_0\cdot(k/g),−y_0\cdot(k/g))$$$ is a solution for the equation $$$cx−dy=k$$$

The general solution can then be given by

In order to find the smallest positive pair of $$$(x,y)$$$ from the above general terms, we compute two pairs $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ where $$$x_1$$$ is the smallest positive integer $$$x$$$ obtained by equating the general term for $$$x$$$ to $$$0$$$ and $$$y_2$$$ is the smallest positive integer $$$y$$$ obtained by equating the general term of $$$y$$$ to $$$0$$$. We then pick the pair such that both $$$x,y \gt =0 $$$ and are the smallest.

#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
 
using namespace std;
 
ll inf = 1e18;
 
vector<ll> extended_euclid(ll a,ll b){
    ll x=1,y=0,x1=0,y1=1;
    while(b){
        ll temp=x,temp1=y;
        x=x1;
        y=y1;
        x1 = temp - (a/b)*x1;
        y1 = temp1 - (a/b)*y1;
        a%=b;
        swap(a,b);
    }
    vector<ll> res(2);
    res[0]=x;
    res[1]=y;
    return res;
}
 
void solve(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    // cx - dy = b+d - (c+a) ; x,y>=0
    ll rhs = b+d -c -a;
    ll g = __gcd(c,d);
    if(rhs%g!=0){
        cout<<-1;
        return;
    }
    ll mult = rhs/g;
    vector<ll> res = extended_euclid(c/g,d/g);
    ll x=res[0]*mult;
    ll y = res[1]*(-mult); // d<0
    // gen sol = (x +- t*d/g, y +- t*c/g) => line with positive slope
    ll ca = d/g;
    ll da = c/g;
 
    // making x>=0
    ll x1 = ((x%ca) + ca)%ca;
    ll y1 = (x1*c-rhs)/d;
 
    // making y>=0
    ll y2 = ((y%da) + da)%da;
    ll x2 = (rhs + y2*d)/c;
 
    ll time=inf;
    
    if(x1>=0 && y1>=0)time=min(time,c*x1+c+a);
    if(x2>=0 && y2>=0) time=min(time,c*x2+c+a);
    cout<<time;
}
 
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}

There are many hints in problem statement.

Groups , Groups are merged

DSU ?

Try to use two different parent vectors in dsu one for path comparison and another for accessing the main parent.

Epiphany 13.0 E1 — New Year Games-1

We have to implement as given in the problem statement: first, for any two groups that face off, we update their win vector, and then we create the next group by merging both groups and updating their score and size from the last two groups.

Only n-1 games play at maximum because if both players are from the same group, then the game is abandoned. As for each time any two groups merge, and in starting, we have n groups, so a maximum of n-1 games are played; all others are abandoned.

        par[next_ind] = next_ind;
        par[a] = next_ind;
        par[b] = next_ind;

        // Update main parent pointers
        par_main[next_ind] = next_ind;
        par_main[a] = next_ind;
        par_main[b] = next_ind;

        // Update score and size information
        score[next_ind] = score[a] + score[b];
        size[next_ind] = size[a] + size[b];

        // Update winner count based on average scores
        if (score[a] / size[a] > score[b] / size[b]) win[a]++;
        if (score[a] / size[a] < score[b] / size[b]) win[b]++;

        // Move to the next index for the new set
        next_ind++;

After playing all games we can find the total win of each person using the main parent vector in total O(n) time

As we are doing path compression using one vector so time complexity of DSU is nearly O(1).

TC = O(n+m)

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

int main() {
    
    // Fast I/O optimization
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;	
	
    // Data structures to manage disjoint sets
    vector<int> score(2 * n + 10);
    vector<int> size(2 * n + 10);
    vector<int> par(2 * n + 10);
    vector<int> par_main(2 * n + 10);
    vector<int> win(2 * n + 10, 0);
    int next_ind = n + 1;

    // Input scores for each player
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
        size[i] = 1;
        par[i] = i;
        par_main[i] = i;
    }

    // Function to find the representative/base of a disjoint set
    function<int(int)> base = [&](int val) {
        if (par[val] == val) return val;
        return par[val] = base(par[val]);	
    };

    // Function to join two disjoint sets
    function<void(int,int)> join = [&](int a, int b) {
        a = base(a);
        b = base(b);
        if (a == b) return;

        // Create a new set and update parent pointers
        par[next_ind] = next_ind;
        par[a] = next_ind;
        par[b] = next_ind;

        // Update main parent pointers
        par_main[next_ind] = next_ind;
        par_main[a] = next_ind;
        par_main[b] = next_ind;

        // Update score and size information
        score[next_ind] = score[a] + score[b];
        size[next_ind] = size[a] + size[b];

        // Update winner count based on average scores
        if (score[a] / size[a] > score[b] / size[b]) win[a]++;
        if (score[a] / size[a] < score[b] / size[b]) win[b]++;

        // Move to the next index for the new set
        next_ind++;
    };
    
    // Process merge operations
    int a, b;
    while (m--) {
        cin >> a >> b;
        join(a, b);
    }

    // Propagate winner information to the main parent
    for (int i = next_ind - 1; i; i--)
        if (par_main[i] != i) win[i] += win[par_main[i]];

    // Output the number of wins for each player
    for (int i = 1; i <= n; i++) cout << win[i] << " ";

    return 0;
}

Epiphany 13.0 E1 — New Year Games-1

Define Basic DSU Structure. In DSU keep arrays also for Score and Length which denotes the score and length of a group where $$$x$$$ is the main parent of the group (score[ $$$x$$$ ], length[ $$$x$$$ ]).

If people $$$x$$$ and $$$y$$$ are playing a game then find the probability of $$$x$$$ and $$$y$$$. Say, avg($$$x$$$) and avg($$$y$$$).

Things to do in DSU:

cnt[ $$$x$$$ ]: Stores the count of $$$winning$$$ of the node $$$x$$$.

Group: Say, Initially, $$$x$$$ & $$$y$$$ playing a game and say avg($$$x$$$) > avg($$$y$$$). So, we make an edge from $$$x$$$ -> $$$y$$$ by storing the id[ $$$x$$$ ] and incrementing cnt[ $$$x$$$ ] by $$$1$$$. (where $$$x$$$ = node which has a higher probability.)

id[ $$$x$$$ ]: id[ $$$x$$$ ] used to give the number to each child of $$$x$$$ according to their joining.

This means, If $$$y$$$ joins $$$x$$$ then id[ $$$x$$$ ] = 1, and the edge will be added like this => adj[ $$$x$$$ ].push_back({$$$y, id[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$y, 1$$$})

after that, If $$$z$$$ joins $$$x$$$, then id[ $$$x$$$ ] = 2 and edge will be added like this => adj[ $$$x$$$ ].push_back({$$$z, id[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$z, 2$$$})

In case, if avg($$$x$$$) = avg($$$y$$$) then do not increment id[ $$$x$$$ ] as we are not incrementing cnt[ $$$x$$$ ].

This id will be used to count the $$$winning$$$ of a $$$node$$$ after it joins the group(where $$$x$$$ = the main parent).

Say, after all the queries id[ $$$x$$$ ] = $$$5$$$, and when $$$z$$$ joined at that time id[ $$$x$$$ ] = $$$2$$$.

It means in total the group of $$$x$$$ wins $$$5$$$ times and ultimately $$$z$$$ wins $$$3$$$ times($$$5$$$ — $$$2$$$) after joining the group.

Things to do in DFS:

Going to every node starting with the nodes who have in-degree = $$$0$$$.

Now at every child of a node, in the child do this: cnt[ $$$child$$$ ] += cnt[ $$$node$$$ ] — $$$id$$$.

Because as explained above if $$$node$$$ has been won $$$5$$$ times and when $$$child$$$ joined at that time $$$id$$$ = $$$2$$$,

then this should be done: cnt[ $$$child$$$ ] += $$$3$$$ => ans[ $$$child$$$ ] += ($$$5$$$ — $$$2$$$) => cnt[ $$$child$$$ ] += (cnt[ $$$node$$$ ] — $$$id$$$).

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

#define endl                                    "\n"
#define int                                     long long

const int M = 1e9 + 7;

const int MX = 1e6 + 5;
vector<array<int, 2>> adj[MX];
vector<int> deg, cnt, id;

void init(int n)
{
	deg.resize(n);
	cnt.resize(n);
	id.resize(n);
}

class DSU{
    public:
    vector<int> par, score, len;
    int n;
    DSU(int sz, vector<int> &s)
    {
        n = sz;
        par.resize(n);
        score.resize(n);
        len.resize(n);
        for(int i = 0; i < n; i++)
        {
            par[i] = i; 
            len[par[i]] = 1;
            score[i] = s[i];
        }
    }

    int find(int node)
    {
        if(node == par[node]) return node;
        return par[node] = find(par[node]);
    }

    int avg(int u)
    {
    	return floor(score[u] / len[u]);
    }
    
    bool merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return u;
        
        if(avg(u) == avg(v))
        {
        	adj[u].push_back({v, id[u]});
        }
        else
        {
        	if(avg(u) < avg(v)) swap(u, v);
        	cnt[u]++;
        	adj[u].push_back({v, ++id[u]});
        }
        
        par[v] = u;
        len[u] += len[v];
        score[u] += score[v];
        deg[v]++;
        
        return u;
    }
};

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> s(n);
	for(int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	init(n);
	DSU d(n, s);
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		x--, y--;
		d.merge(x, y);
	}
	vector<int> v;
	for(int i = 0; i < n; i++)
	{
		if(!deg[i]) v.push_back(i);
	}
	function<void(int)> dfs = [&](int node)
	{
		
		for(auto [child, id] : adj[node])
		{
			cnt[child] += cnt[node] - id;
			dfs(child);
		}
	};
	for(auto it : v) dfs(it);
	for(auto it : cnt) cout << it << " ";
	cout << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
 
    while(t--)
    {
        solve();
    }

    return 0;
}

Epiphany 13.0 E2 — New Year Games-2

There wasn't much difference in E1 and E2 in this problem we have to keep count of probability of win insert of win count.

        // Calculating win probabilities and taking modulo
        int p1 = (score[a] * mod_inverse(size[a], mod)) % mod;
        int p2 = (score[b] * mod_inverse(size[b], mod)) % mod;
 
        int inv = mod_inverse(p1 + p2, mod);
 
        win_prob[a] = (p1 * inv) % mod;
        win_prob[b] = (p2 * inv) % mod;

TC = O(n+m)

// Rutvik Ranpariya

// Including necessary header files
#include <bits/stdc++.h>
using namespace std;

// Defining macro for shorthand notation of long long
#define int long long

// Setting a global constant for modulo operation
int mod = 1e9 + 7;

// Function to calculate extended Euclidean GCD
int extended_euclidean_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    int x1, y1;
    int d = extended_euclidean_gcd(b, a % b, &x1, &y1);

    *x = y1;
    *y = x1 - y1 * (a / b);

    return d;
}

// Function to calculate modular inverse using extended Euclidean algorithm
int mod_inverse(int a, int m) {
    int x, y, d;
    d = extended_euclidean_gcd(a, m, &x, &y);
    if (d != 1)
        return -1;
    return (x % m + m) % m;
}

int32_t main() {
    // Fast I/O optimization
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Input variables for the number of players (n) and the number of pairwise connections (m)
    int n, m;
    cin >> n >> m;

    // Arrays to store scores, sizes, and parent information for each player
    vector<int> score(2 * n + 10);
    vector<int> size(2 * n + 10);
    vector<int> par(2 * n + 10);
    vector<int> par_main(2 * n + 10);
    vector<int> win_prob(2 * n + 10, 0);
    vector<int> count_of_game(2 * n + 10, 0);

    // Variable to keep track of the next available index for a new player
    int next_ind = n + 1;

    // Inputting initial scores and initializing player attributes
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
        size[i] = 1;
        par[i] = i;
        par_main[i] = i;
    }

    // Lambda function to find the base parent of a player
    function<int(int)> base = [&](int val) {
        if (par[val] == val)
            return val;
        return par[val] = base(par[val]);
    };

    // Lambda function to join two players and update the data structures
    function<void(int, int)> join = [&](int a, int b) {
        a = base(a);
        b = base(b);
        if (a == b)
            return;

        // Creating a new player and updating parent information
        par[next_ind] = next_ind;
        par_main[next_ind] = next_ind;
        par[a] = next_ind;
        par[b] = next_ind;
        par_main[a] = next_ind;
        par_main[b] = next_ind;

        // Updating scores and sizes
        score[next_ind] = score[a] + score[b];
        size[next_ind] = size[a] + size[b];

        // Taking modulo of the score to avoid overflow
        score[next_ind] %= mod;

        // Calculating win probabilities and taking modulo
        int p1 = (score[a] * mod_inverse(size[a], mod)) % mod;
        int p2 = (score[b] * mod_inverse(size[b], mod)) % mod;

        int inv = mod_inverse(p1 + p2, mod);

        win_prob[a] = (p1 * inv) % mod;
        win_prob[b] = (p2 * inv) % mod;

        // Incrementing the next available index
        next_ind++;
    };

    // Inputting pairwise connections and joining players accordingly
    int a, b;
    while (m--) {
        cin >> a >> b;
        join(a, b);
    }

    // Array to store the final answer for each player
    vector<int> ans(n + 1, -1);

    // Loop to update win probabilities and count of games played for each player
    for (int i = next_ind - 1; i; i--) {
        if (par_main[i] != i) {
            win_prob[i] += win_prob[par_main[i]];
            count_of_game[i] += count_of_game[par_main[i]] + 1;

            // Taking modulo of the win probability
            win_prob[i] %= mod;

            // Storing the final answer for each player if it is an original player (not created during merging)
            if (i <= n)
                ans[i] = (win_prob[i] * mod_inverse(count_of_game[i], mod)) % mod;
        }
    }

    // Outputting the final answer for each original player
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";

    return 0;
}

Epiphany 13.0 E2 — New Year Games-2

Define Basic DSU Structure. In DSU keep arrays also for Score and Length which denotes the score and length of a group where $$$x$$$ is the main parent of the group (score[ $$$x$$$ ], length[ $$$x$$$ ]).

If people $$$x$$$ and $$$y$$$ are playing a game then find the probability of $$$x$$$ and $$$y$$$. Say, p($$$x$$$) and p($$$y$$$).

My meaning of the term $$$winning$$$ is: that node have a higher probability of winning.

My meaning of the term $$$losing$$$ is: that node have a lower probability of winning.

Things to do in DSU:

cnt[ $$$x$$$ ]: Stores the total number of games played by $$$x$$$.

Group: Say, Initially, $$$x$$$ & $$$y$$$ playing a game and say p($$$x$$$) > p($$$y$$$). So, we make an edge from $$$x$$$ -> $$$y$$$ by storing the id[ $$$x$$$ ] and incrementing cnt[ $$$x$$$ ] by $$$1$$$. (where $$$x$$$ = node which has a higher probability.)

ans[ $$$x$$$ ]: Stores the sum of the probabilities when the node $$$x$$$ was $$$winning$$$.

Similar concept as the $$$id$$$ that if in the group of $$$x$$$ if $$$y$$$ joins then we need to remove current ans[ $$$x$$$ ] from the final ans[ $$$x$$$ ] as only the sum of probability after joining of $$$y$$$ added to the ans [ $$$y$$$ ]. To do this we add current ans[ $$$x$$$ ] to the adjacency list when we make the edge and we do this after understanding the $$$id$$$.

val[ $$$x$$$ ]: Stores the sum of the probabilities when the node $$$x$$$ was $$$losing$$$.

The val[ $$$x$$$ ] should be directly added to all the children and grandchildren till the leaf node as if any node $ loses any time then that node never represents the group some other node will come into the picture. So, no need to store current value and stuff.

id[ $$$x$$$ ]: id[ $$$x$$$ ] used to give the number to each child of $$$x$$$ according to their joining.

This means, If $$$y$$$ joins $$$x$$$ then id[ $$$x$$$ ] = 1, and the edge will be added like this => adj[ $$$x$$$ ].push_back({$$$y, id[x], ans[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$y, 1, ans[x]$$$})

after that, If $$$z$$$ joins $$$x$$$, then id[ $$$x$$$ ] = 2 and edge will be added like this => adj[ $$$x$$$ ].push_back({$$$z, id[x], ans[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$z, 2, ans[x]$$$})

This id will be used to count the number of games played by a $$$node$$$ after it joins the group(where $$$x$$$ = the main parent).

Say, after all the queries id[ $$$x$$$ ] = $$$5$$$, and when $$$z$$$ joined at that time id[ $$$x$$$ ] = $$$2$$$.

It means in total the group of $$$x$$$ played $$$5$$$ games and ultimately $$$z$$$ played $$$4$$$ times($$$5$$$ — $$$2$$$) + $$$1$$$ after playing the match and joining the group.

Things to do in DFS:

Going to every node starting with the nodes who have in-degree = $$$0$$$.

Now at every child of a node, in the child do this: cnt[ $$$child$$$ ] += cnt[ $$$node$$$ ] — $$$id$$$ + $$$1$$$.

Because as explained above if $$$node$$$ has been won $$$5$$$ times and when $$$child$$$ joined at that time $$$id$$$ = $$$2$$$,

then this should be done: cnt[ $$$child$$$ ] += $$$3$$$ => cnt[ $$$child$$$ ] += ($$$5$$$ — $$$2$$$) => cnt[ $$$child$$$ ] += (cnt[ $$$node$$$ ] — $$$id$$$) + $$$1$$$.

Also,at every child of a node, in the child also do this: ans[ $$$child$$$ ] += ans[ $$$node$$$ ] — ans_till_child. (ans_till_child = Stored answer at the time of edge was created.)

Also, at every child of a node, in the child also do this: ans[ $$$child$$$ ] += val[ $$$child$$$ ]. (Adding the $$$losing$$$ probability.)

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

#define endl                                    "\n"
#define int                                     long long

const int M = 1e9 + 7;

int gcdExtended(int a, int b, int* x, int* y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    int x1, y1; 
    int gcd = gcdExtended(b % a, a, &x1, &y1); 
    *x = y1 - (b / a) * x1; 
    *y = x1; 
    return gcd; 
} 
 
int inv(int a) 
{ 
    int x, y; 
    int g = gcdExtended(a, M, &x, &y); 
    return (x % M + M) % M;
}

const int MX = 1e6 + 5;
vector<array<int, 3>> adj[MX];
vector<int> deg, ans, val, id, cnt;

void init(int n)
{
	deg.resize(n);
	ans.resize(n);
	val.resize(n);
	id.resize(n);
	cnt.resize(n);
}  

void add_self(int &a, int b)
{
	a += b;
	if(a >= M) a -= M;
}

int add(int a, int b)
{
	return (a + b) % M;
}

int sub(int a, int b)
{
	return (a - b + M) % M;
}

int mul(int a, int b)
{
	return (a * b) % M;
}
 
class DSU{
    public:
    vector<int> par, score, len;
    int n;
    DSU(int sz, vector<int> &s)
    {
        n = sz;
        par.resize(n);
        score.resize(n);
        len.resize(n);
        for(int i = 0; i < n; i++)
        {
            par[i] = i; 
            len[i] = 1;
            score[i] = s[i];
        }
    }
 
    int find(int node)
    {
        if(node == par[node]) return node;
        return par[node] = find(par[node]);
    }
 
    int team_score(int u)
    {
    	return mul(score[u], inv(len[u]));
    }
    
    int prob(int u, int v)
    {
    	int s_u = team_score(u);
    	int s_v = team_score(v);
    	return mul(s_u, inv(add(s_u, s_v)));
    }
    
    bool merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return u;
        int u_v = prob(u, v);
        int v_u = prob(v, u);
        if(u_v == v_u)
        {   
        	add_self(ans[u], u_v);
        	add_self(ans[v], u_v);
        	adj[u].push_back({v, ans[u], ++id[u]});
        }
        else
        {
        	if(u_v < v_u) swap(u, v), swap(u_v, v_u);
	        add_self(ans[u], u_v);
	        add_self(val[v], v_u);
	        adj[u].push_back({v, ans[u], ++id[u]});
        }
        par[v] = u;
        add_self(len[u], len[v]);
        add_self(score[u], score[v]);
        deg[v]++;
        cnt[u]++;
        
        return u;
    }
};
 
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> s(n);
	for(int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	init(n);
	DSU d(n, s);
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		x--, y--;
		d.merge(x, y);
	}
	vector<int> v;
	for(int i = 0; i < n; i++)
	{
		if(!deg[i]) v.push_back(i);
	}
	
	function<void(int)> dfs = [&](int node)
	{	
		for(auto [child, ans_till_child, id] : adj[node])
		{
			add_self(ans[child], sub(ans[node], ans_till_child));
			add_self(ans[child], val[child]);
			add_self(cnt[child], sub(cnt[node], id) + 1);
			dfs(child);
		}
	};
	for(auto it : v) dfs(it);
	for(int i = 0; i < n; i++)
	{
		if(!cnt[i]) cout << -1 << " ";
		else cout << mul(ans[i], inv(cnt[i])) << " ";
	} 
	cout << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
 
    while(t--)
    {
        solve();
    }

    return 0;
}

Divide the given tree into components using Heavy-Light Decomposition

Apply lazy segment tree on each component or chain to store and get $$$(a, b)$$$ for the ranges.

Notice the condition $$$q*k \le 5\cdot10^7$$$.

For each node in the path from $$$u$$$ to $$$v$$$ run a query on the segment tree for each query of Type-2 for $$$logN$$$ time to get the value of $$$(a, b)$$$ of the range $$$[x, x]$$$ Where $$$x$$$ is the node in the path from $$$u$$$ to $$$v$$$. Now, the path from $$$u$$$ to $$$v$$$ takes time-$$$K$$$ and each node takes $$$logN$$$ for $$$Q$$$ times.

Epiphany 13.0 F — Money Distribution

Define the basic Heavy-Light Decomposition structure . Where each node will get Id's according to the heavy and light edges by doing a DFS traversal.

For Type-1 Query: If $$$u$$$ and $$$v$$$ are in the same chain then add the value pair $$$(a, b)$$$ to all the nodes in the chain of $$$u$$$ and $$$v$$$ using the lazy segment tree of that chain.

Otherwise, according to depth, choose a node from $$$u$$$ and $$$v$$$ such that the depth of the head of the node is higher and add the value pair $$$(a, b)$$$ to all the nodes of the chain in which the chosen node lies(using the lazy segment tree of that chain). Do this till both the nodes come to the same chain.

For Type-2 Query: If $$$u$$$ and $$$v$$$ are in the same chain then run a loop from Id[head[u]] to Id[u] (Assume that depth[head[u]] > depth[head[v]]) and run a query on the segment tree of that chain till the leaf node where the range is $$$[x, x]$$$ only. Where $$$x$$$ is the Id of the node in the path from $$$u$$$ to $$$v$$$.

Keep two answer variables initially initialized with $$$0$$$ and each will store the answer of either the left or the right side of the $$$LCA(u, v)$$$.

Now, take value pair $$$(a, b)$$$ from the segment tree node for the range $$$[x, x]$$$ and add $$$st[node].a * Id[x] + st[node].b$$$ to the appropriate answer variable the left or the right.

If $$$u$$$ and $$$v$$$ are not in the same chain then choose a node such that the head of the node has the higher depth and apply the above operation of query on the chain of the current node.

At last, return the $$$XOR$$$ of both the answer variables.

T.C: $$$O(Q * (K + logn) * logn)$$$

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

#define endl                                    "\n"
#define int                                     long long
#define all(a)                                  a.begin(), a.end()

struct value{
	int a, b;
};
 
class HLD{
	public:
	vector<int> head, heavy, depth, parent, id;
	int id_num;
	vector<value> st, lazy;
	int n;
	map<pair<int, int>, int> map_node;
	vector<int> map_val;
	
	HLD(int sz, vector<int> *adj)
	{
		n = sz;
		head.resize(n + 1);
		heavy.resize(n + 1, -1);
		depth.resize(n + 1);
		parent.resize(n + 1);
		id.resize(n + 1);
		map_val.resize(n);
		id_num = 0;
		dfs_sz(0, adj);
		dfs_hld(0, 0, adj);
		map_vals();
		
		st.resize(4 * n);
		lazy.resize(4 * n);
		build(0, 0, n - 1);
	}
	
	value move(value x, value y)
	{
		return {x.a + y.a, x.b + y.b};
	}
	
	void build(int node, int start, int end)
	{
		if(start == end)
		{
			map_node[{start, end}] = node;
			return;
		}
		int mid = (start + end) >> 1;
		build(2 * node + 1, start, mid);
		build(2 * node + 2, mid + 1, end);
	}
	
	void push(int x, int y, int node, int start, int end)
	{
		st[node].a += (end - start + 1) * x;
		st[node].b += (end - start + 1) * y;
		if(start != end)
		{
			lazy[2 * node + 1].a += x;
			lazy[2 * node + 1].b += y;
			lazy[2 * node + 2].a += x;
			lazy[2 * node + 2].b += y;
		}
		lazy[node].a = lazy[node].b = 0;
	}
	
	void update(int node, int start, int end, int l, int r, value p)
	{
		if(lazy[node].a != 0 || lazy[node].b != 0)
		{
			push(lazy[node].a, lazy[node].b, node, start, end);
		}
		if(start > r || end < l) return;
		if(l <= start && end <= r) 
		{
			push(p.a, p.b, node, start, end);
			return;
		}
		int mid = (start + end) >> 1;
		update(2 * node + 1, start, mid, l, r, p);
		update(2 * node + 2, mid + 1, end, l, r, p);
		st[node] = move(st[2 * node + 1], st[2 * node + 2]);
	}
	
	value query(int node, int start, int end, int l, int r)
	{
		if(lazy[node].a != 0 || lazy[node].b != 0)
		{
			push(lazy[node].a, lazy[node].b, node, start, end);
		}
		if(start > r || end < l) return {};
		if(start == end) return st[node];
		int mid = (start + end) >> 1;
		value left = query(2 * node + 1, start, mid, l, r);
		value right = query(2 * node + 2, mid + 1, end, l, r);
		return move(left, right);
	}
		
	int dfs_sz(int node, vector<int> *adj)
	{
		int sz = 1, mx = 0;
		for(auto it : adj[node])
		{
			if(it == parent[node]) continue;
			
			parent[it] = node, depth[it] = depth[node] + 1;
			int child_sz = dfs_sz(it, adj);
			sz += child_sz;
			if(child_sz > mx)
			{
				mx = child_sz;
				heavy[node] = it;
			}
		}
		return sz;
	}
	
	void dfs_hld(int node, int top, vector<int> *adj)
	{
		head[node] = top;
		id[node] = id_num++;
		if(heavy[node] != -1) dfs_hld(heavy[node], top, adj);
		for(auto it : adj[node])
		{
			if(it == parent[node] || it == heavy[node]) continue;
			dfs_hld(it, it, adj);
		}
	}
	
	void map_vals()
	{
		for(int i = 0; i < n; i++) map_val[id[i]] = i + 1;
	}
	
	void update_path(int u, int v, value p)
	{
		while(head[u] != head[v])
		{
			if(depth[head[u]] > depth[head[v]]) swap(u, v);
			
			update(0, 0, n - 1, id[head[v]], id[v], p);
			
			v = parent[head[v]];
		}
		if(depth[u] > depth[v]) swap(u, v);
		
		update(0, 0, n - 1, id[u], id[v], p);
	}
	
	int query_path(int u, int v)
	{
		int ansv = 0, ansu = 0;
		while(head[u] != head[v])
		{
			if(depth[head[u]] > depth[head[v]]) swap(u, v), swap(ansv, ansu);
			
			int x = id[head[v]], y = id[v];
			for(int i = x; i <= y; i++)
			{
				query(0, 0, n - 1, i, i);
				int node = map_node[{i, i}];
				int val = map_val[i];
				ansv += st[node].a * val + st[node].b;
			}
						
			v = parent[head[v]];
		}
		
		if(depth[u] > depth[v]) swap(u, v), swap(ansv, ansu);
		
		int x = id[u], y = id[v];
		for(int i = x; i <= y; i++)
		{
			query(0, 0, n - 1, i, i);
			int node = map_node[{i, i}];
			int val = map_val[i];
			ansv += st[node].a * val + st[node].b;
			if(i == x) ansu += st[node].a * val + st[node].b;
		}
		return ansv ^ ansu;
	}
};
 
void solve()
{
	int n, q;
	cin >> n >> q;
	vector<int> adj[n];
	for(int i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	HLD hld(n, adj); 
	
	while(q--)
	{
		int type;
		cin >> type;
		if(type == 1)
		{
			int u, v, a, b;
			cin >> u >> v >> a >> b;
			u--, v--;
			hld.update_path(u, v, {a, b});
		}
		else
		{
			int u, v;
			cin >> u >> v;
			u--, v--;
			cout << hld.query_path(u, v) << endl;
		}
	}
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1; 
    while(t--)
    {
        solve();
    }
 
    return 0;
}

T.C: $$$O(Q * (K + logn) * logn)$$$

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

#define endl                                    "\n"
#define int                                     long long

struct value{
	int a, b;
};

struct node{
	int val, sz, sum, a, b;
};

class HLD{
	public:
	vector<int> head, heavy, depth, parent, id, map_val;
	vector<node> st;
	int id_num;
	int n;
	HLD(int sz, vector<int> adj[])
	{
		n = sz;
		head.resize(n + 1);
		heavy.resize(n + 1, -1);
		depth.resize(n + 1);
		parent.resize(n + 1);
		id.resize(n + 1);
		map_val.resize(n + 1);
		id_num = 0;
		dfs_sz(0, adj);
		dfs_hld(0, 0, adj);
		map_vals();
		
		st.resize(4 * n);
	}
	
	void print()
	{
		for(int i = 0; i < n; i++)
		{
			cout << i + 1 << " " << map_val[i] << endl; // id, node.
		}
	}
	
	void map_vals()
	{
		for(int i = 0; i < n; i++) map_val[id[i]] = i + 1;
	}

	int dfs_sz(int node, vector<int> adj[])
	{
		int sz = 1, mx = 0;
		for(auto it : adj[node])
		{
			if(it == parent[node]) continue;
			
			parent[it] = node, depth[it] = depth[node] + 1;
			int child_sz = dfs_sz(it, adj);
			sz += child_sz;
			if(child_sz > mx)
			{
				mx = child_sz;
				heavy[node] = it;
			}
		}
		return sz;
	}
	
	void dfs_hld(int node, int top, vector<int> adj[])
	{
		head[node] = top;
		id[node] = id_num++;
		if(heavy[node] != -1) dfs_hld(heavy[node], top, adj);
		for(auto it : adj[node])
		{
			if(it == parent[node] || it == heavy[node]) continue;
			dfs_hld(it, it, adj);
		}
	}
	
	void push(int node)
	{
		st[2 * node + 1].a += st[node].a; 
		st[2 * node + 1].b += st[node].b; 
		st[2 * node + 1].val += st[node].a * st[2 * node + 1].sum + st[node].b * st[2 * node + 1].sz;
		st[2 * node + 2].a += st[node].a; 
		st[2 * node + 2].b += st[node].b; 
		st[2 * node + 2].val += st[node].a * st[2 * node + 2].sum + st[node].b * st[2 * node + 2].sz;
		st[node].a = st[node].b = 0;
	}
	
	void set(int node, int start, int end, int i, int val)
	{
		if(start > i || end < i) return;
		if(start == end) 
		{
			st[node].sum = val;
			st[node].sz = 1;
			return;
		}
		int mid = (start + end) >> 1;
		
		if(st[node].a || st[node].b) push(node);
		
		set(2 * node + 1, start, mid, i, val);
		set(2 * node + 2, mid + 1, end, i, val);
		
		st[node].sum = st[2 * node + 1].sum + st[2 * node + 2].sum;
		st[node].sz = st[2 * node + 1].sz + st[2 * node + 2].sz;
		st[node].val = st[2 * node + 1].val + st[2 * node + 2].val;
	}
	
	void update(int node, int start, int end, int l, int r, value p)
	{
		if(start > r || end < l) return;
		if(l <= start && end <= r) 
		{
			st[node].val += p.a * st[node].sum + p.b * st[node].sz;
			st[node].a += p.a;
			st[node].b += p.b;
			return;
		}
		
		int mid = (start + end) >> 1;
		
		if(st[node].a || st[node].b) push(node);
		
		update(2 * node + 1, start, mid, l, r, p);
		update(2 * node + 2, mid + 1, end, l, r, p);
		
		st[node].val = st[2 * node + 1].val + st[2 * node + 2].val;
	}
	
	int query(int node, int start, int end, int l, int r)
	{
		if(start > r || end < l) return 0ll;
		if(l <= start && end <= r) return st[node].val;
		int mid = (start + end) >> 1;
		
		if(st[node].a || st[node].b) push(node);
		
		int left = query(2 * node + 1, start, mid, l, r);
		int right = query(2 * node + 2, mid + 1, end, l, r);
		return left + right;
	}
	
	void update_path(int u, int v, value p)
	{
		while(head[u] != head[v])
		{
			if(depth[head[u]] > depth[head[v]]) swap(u, v);
			
			update(0, 0, n - 1, id[head[v]], id[v], p);
			
			v = parent[head[v]];
		}
		if(depth[u] > depth[v]) swap(u, v);
		
		update(0, 0, n - 1, id[u], id[v], p);
	}
	
	int query_path(int u, int v)
	{
		int ans = 0;
		while(head[u] != head[v])
		{
			if(depth[head[u]] > depth[head[v]]) swap(u, v);
			
			ans += query(0, 0, n - 1, id[head[v]], id[v]);
			
			v = parent[head[v]];
		}
		if(depth[u] > depth[v]) swap(u, v);
		
		return ans += query(0, 0, n - 1, id[u], id[v]);
	}
};

class binlift{
	public:
	int n, l, timer;
	vector<int> tin, tout;
	vector<vector<int>> dp;
	binlift(int sz, int root, vector<int> adj[])
	{
		n = sz;
		l = ceil(log2(n));
		timer = 0;
		tin.resize(n + 1);
		tout.resize(n + 1);
		dp.resize(n + 1, vector<int> (l + 1));
		dfs(root, root, adj);
	}
	
	void dfs(int node, int par, vector<int> adj[])
	{
		tin[node] = ++timer;
		dp[node][0] = par;
		for(int j = 1; j <= l; j++) dp[node][j] = dp[dp[node][j - 1]][j - 1];
		for(auto it : adj[node])
		{
			if(it == par) continue;
			dfs(it, node, adj);
		}
		tout[node] = ++timer;
	}
	
	bool is_ancestor(int u, int v)
	{
		return (tin[u] <= tin[v] && tout[u] >= tout[v]);
	}
	
	int lca(int u, int v)
	{
		if(is_ancestor(u, v)) return u;
		if(is_ancestor(v, u)) return v;
		for(int j = l; j >= 0; j--)
		{
			if(is_ancestor(dp[u][j], v)) continue;
			u = dp[u][j];
		}
		return dp[u][0];
	}
};

void solve()
{
	int n, q;
	cin >> n >> q;
	vector<int> adj[n];
	for(int i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	HLD hld(n, adj);
	for(int i = 0; i < n; i++) hld.set(0, 0, n - 1, hld.id[i], i + 1);
	
	binlift bin(n, 0, adj);
	
	while(q--)
	{
		int type;
		cin >> type;
		if(type == 1)
		{
			int u, v, a, b;
			cin >> u >> v >> a >> b;
			u--, v--;
			hld.update_path(u, v, {a, b});
		}
		else
		{
			int u, v;
			cin >> u >> v;
			u--, v--;
			int lca = bin.lca(u, v);
			int a = hld.query_path(u, lca);
			int b = hld.query_path(v, lca);
			cout << (a ^ b) << endl;
		}
	}
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
 
    while(t--)
    {
        solve();
    }

    return 0;
}

T.C: $$$O(Q * logn * logn)$$$