We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Easy Addition
  5. Discussions

Easy Addition

Sort by

recency

|

8 Discussions

|

  • writersera21
     + 0 comments

    To solve this problem efficiently, we can use a data structure called a segment tree. A segment tree is a binary tree that represents an array. This is the ninja moba way to solve this problem. Each node of the segment tree stores the sum of a range of elements from the original array.

    Here's how we can approach the problem using a segment tree:

    Create an adjacency list to represent the tree based on the given edges.

    Build the segment tree using the adjacency list and assign initial values of zero to all nodes.

    Process the update queries:

    For each update query, traverse the path from node A to node B using a depth-first search (DFS) or any other graph traversal algorithm. Update the segment tree nodes along the path by adding the value (a1 + distance * d1) to each node, where the distance is the distance from the current node to node A. Repeat the above step for each update query. Process the retrieval queries:

    For each retrieval query, traverse the path from node i to node j using a DFS or any other graph traversal algorithm. Calculate the sum of the values in the segment tree nodes along the path. Take the modulo 1000000007 of the sum and output the result. Here's the implementation in Python:

    MOD = 1000000007

# Function to build the segment tree
def build_segment_tree(adj_list, node, start, end, values):
    if start == end:
        adj_list[node] = [start]
        values[node] = 0
    else:
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2

        build_segment_tree(adj_list, left_child, start, mid, values)
        build_segment_tree(adj_list, right_child, mid + 1, end, values)

        adj_list[node] = adj_list[left_child] + adj_list[right_child]
        values[node] = 0

# Function to update the segment tree
def update_segment_tree(adj_list, values, node, start, end, update_start, update_end, a1, d1):
    if start > update_end or end < update_start:
        return

    if start >= update_start and end <= update_end:
        for idx in adj_list[node]:
            distance = abs(idx - update_start)
            values[idx] = (values[idx] + a1 + distance * d1) % MOD
        return

    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2

    update_segment_tree(adj_list, values, left_child, start, mid, update_start, update_end, a1, d1)
    update_segment_tree(adj_list, values, right_child, mid + 1, end, update_start, update_end, a1, d1)

# Function to retrieve the sum from the segment tree
def retrieve_segment_tree(adj_list, values, node, start, end, retrieve_start, retrieve_end, total_sum):
    if start > retrieve_end or end < retrieve_start:
        return

    if start >= retrieve_start and end <= retrieve_end:
        for idx in adj_list[node]:
            total_sum = (total_sum + values[idx]) % MOD
        return total_sum

    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2

    total_sum = retrieve_segment_tree(adj_list, values, left_child, start, mid, retrieve_start, retrieve_end, total

  • TChalla
     + 0 comments

    C++ Solution

    #include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
typedef long long int ll;

const int mod = 1000000007;
vector<int> myvector[100001];
int N, parent[100001], depth[100001], Q, U;
ll R, Rinv, Rp[100001], sum[100001];
int store[100001], Root[100001][18];

struct node{
    ll S, D, B, factD, factB, addB;
    node(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0){
        S = a, D = b, B = c;
        factD = d;
        factB = e;
        addB = f;
    }
    
    node operator + (const node &x) const{
        ll a, b, c, d, e, f;
        a = (x.S + S);
        b = (x.D + D);
        c = (x.B + B);
        d = (x.factD + factD);
        e = (x.factB + factB);
        f = (x.addB + addB);
        a = (a > mod) ? (a - mod) : a;
        b = (b > mod) ? (b - mod) : b;
        c = (c > mod) ? (c - mod) : c;
        d = (d > mod) ? (d - mod) : d;
        e = (e > mod) ? (e - mod) : e;
        f = (f > mod) ? (f - mod) : f;
        return node(a, b, c, d, e, f);
    }
    
} fwd[100001], bck[100001], A, B;

ll inverse(ll a, ll b){
    ll Remainder, p0 = 0, p1 = 1, pcurr = 1, q, m = b;
    while(a != 0){
        Remainder = b % a;
        q = b / a;
        if(Remainder != 0){
            pcurr = p0 - (p1 * q) % m;
            if(pcurr < 0)
                pcurr += m;
            p0 = p1;
            p1 = pcurr;
        }
        b = a;
        a = Remainder;
    }
    return pcurr;   
}

void dfs_pre(int root){
    for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
        if(parent[root] == *it) continue;
        parent[*it] = root;
        depth[*it] = depth[root] + 1;
        dfs_pre(*it);
    }
}

void dfs_cal(int root){
    for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
        if(parent[root]==*it) continue;
        dfs_cal(*it);
        fwd[root].S = (fwd[root].S + fwd[*it].S * R) % mod;
        fwd[root].D = (fwd[root].D + (fwd[*it].D + fwd[*it].factD) * R) % mod;
        fwd[root].factD = (fwd[root].factD + fwd[*it].factD * R) % mod;
        fwd[root].B = (fwd[root].B +  (fwd[*it].B + fwd[*it].factB) * R) % mod;
        fwd[root].factB = (fwd[root].factB + (fwd[*it].factB + fwd[*it].addB) * R) % mod;
        fwd[root].addB = (fwd[root].addB + fwd[*it].addB * R) % mod;
        bck[root].S = (bck[*it].S * Rinv + bck[root].S) % mod;
        bck[root].D = (bck[root].D + (bck[*it].D - bck[*it].factD) * Rinv) % mod;
        if(bck[root].D < 0) bck[root].D += mod;
        bck[root].factD = (bck[root].factD + bck[*it].factD * Rinv) % mod; 
        bck[root].B = (bck[root].B + (bck[*it].B - bck[*it].factB) * Rinv) % mod; 
        if(bck[root].B<0) bck[root].B += mod;
        bck[root].factB = (bck[root].factB + (bck[*it].factB - bck[*it].addB) * Rinv) % mod;
        if(bck[root].factB<0) bck[root].factB += mod;
        bck[root].addB = (bck[root].addB + bck[*it].addB * Rinv) % mod;
    }
    sum[root] = (sum[root] + fwd[root].S + fwd[root].D + fwd[root].B + bck[root].S + bck[root].D + bck[root].B) % mod;
}

void dfs_sum(int root)      {
    for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
        if(parent[root] == *it) continue;
        sum[*it] = (sum[*it] + sum[root]) % mod;
        dfs_sum(*it);
    }
}

void init(){
    store[0] = 0; store[1] = 0; store[2] = 1;
    int cmp = 4;
    FOR(i, 3, 100000){
        if(cmp > i) store[i] = store[i - 1];
        else{
            store[i] = store[i - 1] + 1;
            cmp <<= 1;
        }
    }
}

void process(int N){
    memset(Root, -1, sizeof(Root));
    for(int i = 1; i <= N; i++) Root[i][0]=parent[i];
    for(int i = 1; (1 << i) <= N; i++)
        for(int j = 1; j <= N; j++)
            if(Root[j][i - 1] != -1)
                Root[j][i] = Root[Root[j][i - 1]][i - 1];
}

int lca(int p, int q){
    int temp;
    if(depth[p] > depth[q]) swap(p, q);
    int steps = store[depth[q]];
    for(int i = steps; i >= 0; i--)
        if(depth[q] - (1 << i) >= depth[p])
            q = Root[q][i];
    if(p == q) return p;
    for(int i = steps; i >= 0; i--){
    if(Root[p][i] != Root[q][i])
        p = Root[p][i], q = Root[q][i];
    }
    return parent[p];
}

void Update_forward(ll S, ll D, ll B1, ll t, int x, int y){
    ll brt;
    A.S = S;
    B.S = mod - (S * Rp[t]) % mod;
    A.factD = D;
    A.D = 0;
    B.factD = mod - (D * Rp[t]) % mod;
    if(B.factD < 0) B.factD += mod;
    B.D = (B.factD * t) % mod;
    brt = B1;
    A.B = 0;
    A.factB = brt;
    if(A.factB < 0) A.factB += mod;
    A.addB = (brt + brt) % mod;
    brt = mod - (B1 * Rp[t]) % mod;
    if(brt < 0) brt += mod;
    B.B = ((ll)((t * t) % mod) * brt) % mod;
    B.factB = ((ll)(2 * t + 1) * brt) % mod;
    B.addB = (brt + brt) % mod;
    fwd[x] = fwd[x] + A;
    if(y != 1) fwd[parent[y]] = fwd[parent[y]] + B;
}

void Update_backward(ll S,ll D,ll B1,ll t,ll g,int y,int x){
    ll brt;
    B.S = (S * Rp[t]) % mod;
    A.S = mod - (S * Rp[g]) % mod;
    B.factD = (D * Rp[t]) % mod;
    B.D = (t * B.factD) % mod;
    A.factD = mod - (D * Rp[g]) % mod;
    A.D = (g * A.factD) % mod;
    brt = (B1 * Rp[t]) % mod;
    B.addB = brt + brt;
    if(B.addB >= mod) B.addB -= mod;
    B.factB = ((ll)(2 * t - 1) * brt) % mod;
    if(B.factB < 0) B.factB += mod;
    B.B = ((ll)((t * t) % mod) * brt) % mod;
    brt = mod - (B1 * Rp[g]) % mod;
    if(brt < 0) brt += mod;
    A.addB = brt + brt;
    if(A.addB >= mod) A.addB -= mod;
    A.factB = ((ll)(2 * g - 1) * brt) % mod;
    if(A.factB < 0) A.factB += mod; 
    A.B = ((ll)((g * g) % mod) * brt) % mod;
    bck[y] = bck[y] + B;
    bck[x] = bck[x] + A;
}

void solve(){
    ll S1, D1, B1, ans;
    int Z, anc, x, y, a1, a2, d1, d2;
    scanf("%d%lld", &N, &R);
    Rinv = inverse(R, mod);
    FOR(i, 1, N - 1){
        scanf("%d%d", &x, &y);
        myvector[x].push_back(y);
        myvector[y].push_back(x);
    }
    parent[1] = 1;
    depth[1] = 0;
    dfs_pre(1);
    process(N);
    Rp[0] = 1;
    FOR(i, 1, N) Rp[i] = ((ll)Rp[i - 1] * (ll)R) % mod;
    scanf("%d%d", &U, &Q);
    while(U--){
        scanf("%d%d%d%d%d%d", &a1, &d1, &a2, &d2, &x, &y);
        S1 = ((ll)a1 * (ll)a2) % mod;
        D1 = ((ll)d1 * (ll)a2 + (ll)d2 * (ll)a1) % mod;
        B1 = ((ll)d1 * (ll)d2) % mod;
        anc = lca(x, y);
        Update_forward(S1, D1, B1, depth[x] - depth[anc] + 1, x, anc);
        Update_backward(S1, D1, B1, depth[y] + depth[x] - 2 * depth[anc], depth[x] - depth[anc], y, anc);
    }
    dfs_cal(1);
    dfs_sum(1);
    while(Q--){ 
        scanf("%d%d", &x, &y);
        anc = lca(x, y);
        if(anc != 1) ans = (sum[x] + sum[y] - sum[anc] - sum[parent[anc]]) % mod;
        else ans = (sum[x] + sum[y] - sum[anc]) % mod;
        if(ans < 0) printf("%lld\n", ans + mod);
        else printf("%lld\n", ans);
    }
}

int main(){
    init();
    solve();
    return 0;
}

  • yashpalsinghdeo1
     + 0 comments

    for complete solution in python java c++ and c programming search for programs.programmingoneonone.com on google

  • farshad_afshari
     + 1 comment

    I can't find how the query between the sum of weights between 5 and 3 is 9. The path would be 5,4,1,3 and the second path is 5,4,2,1,3. Why the longer path considered a solution?

                      1
       /|\
      | 2 3
       \ |\
        4 6
        | |
        5 7

  • phibrain
     + 0 comments

    the problem could be more interesting if the queries are done in random order... a hld aproach will be necesary...