HackerEarth 3B - Bear and Special Dfs solution

In this HackerEarth 3B – Bear and Special Dfs problem solution Bear recently studied the depth first traversal of a Tree in his Data Structure class. He learnt the following algorithm for doing a dfs on a tree.

void dfs(int v,int p){

vis[v] = 1;

for(int i=0;i<G[v].size();++i){

if(G[v][i]!=p)

dfs(G[v][i],v);

}

Now he was given an array A, Tree G as an adjacency list and Q queries to answer on the following modified algorithm as an homework.

void dfs(int v,int p){

vis[v] += 1;

for(int j=1;j<=A[v];++j){

for(int i=0;i<G[v].size();++i){

if(G[v][i]!=p)

dfs(G[v][i],v);

}

The Q queries can be of the following two types :

v x : Update A[v] = x. Note that updates are permanent.
v: Initialize vis[u] = 0 u related[1,N]. Run the above algorithm with call dfs(1,-1). Compute the sum Sigma(u related subtree of v, v) vis[u]. As the result may be quite large print it mod 10^9 + 7.

HackerEarth 3B – Bear and Special Dfs problem solution.

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fre     freopen("0.in","r",stdin);freopen("0.out","w",stdout)
#define abs(x) ((x)>0?(x):-(x))
#define MOD 1000000007
#define LL signed long long int
#define pii pair<int,int>
#define scan(x) scanf("%d",&x)
#define print(x) printf("%dn",x)
#define scanll(x) scanf("%lld",&x)
#define printll(x) printf("%lldn",x)
#define rep(i,from,to) for(int i=(from);i <= (to); ++i)
vector<int> G[2*100000+5];
int L[100000+5],R[100000+5], A[100000+5];
LL tree[5*100000+5];
LL lazy[5*100000+5];
int T = 0;
void dfs(int v,int p){
    L[v] = ++T;
    for(int i=0;i<G[v].size();++i){
        int u = G[v][i];
        if(u==p)
            continue;
        dfs(u,v);
    }
    R[v] = T;
}

LL pow(LL base, LL exponent,LL modulus)
{
    LL result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

void build(int i,int si,int sj){
    if(si==sj){
        tree[i] = 1;
        lazy[i] = 1;
    }
    else{
        int mid = (si+sj)/2;
        build(2*i,si,mid);
        build(2*i+1,mid+1,sj);
        tree[i] = tree[2*i]+tree[2*i+1];
        lazy[i] = 1;
    }
}
void update(int i,int si,int sj,int qi,int qj,int x){
    if(si==qi and sj==qj){
        tree[i] = tree[i] * x % MOD;
        lazy[i] = lazy[i] * x % MOD;
    }
    else{
        int mid = (si+sj)/2;
        if(qj<=mid)
            update(2*i,si,mid,qi,qj,x);
        else if(mid+1<=qi)
            update(2*i+1,mid+1,sj,qi,qj,x);
        else
            update(2*i,si,mid,qi,mid,x),
            update(2*i+1,mid+1,sj,mid+1,qj,x);
        tree[i] = (tree[2*i] + tree[2*i+1]) * lazy[i] % MOD;
    }
}
LL query(int i,int si,int sj,int qi,int qj){
    if(qi==si and qj==sj){
        return tree[i];
    }
    else{
        int mid = (si+sj)/2;
        LL x = 0;
        if(qj<=mid)
            x = query(2*i,si,mid,qi,qj);
        else if(mid+1<=qi)
            x = query(2*i+1,mid+1,sj,qi,qj);
        else
            x = query(2*i,si,mid,qi,mid) + query(2*i+1,mid+1,sj,mid+1,qj);
        return x * lazy[i] % MOD;
    }
}
int N;
void update(int i,int j,int x){
    if(i<=j){
        update(1,1,N,i,j,x);
    }
}

int main(){
    //fre;
    int Q,a,b,c,x,v;
    cin>>N>>Q;
    rep(i,1,N-1){
        scan(a);
        scan(b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    build(1,1,N);
    rep(i,1,N)scan(A[i]),update(L[i]+1,R[i],A[i]);
    while(Q--){
        scan(c);
        if(c==1){
            //update
            scan(v);
            scan(x);
            update(L[v]+1,R[v],pow(A[v],MOD-2,MOD));
            A[v] = x;
            update(L[v]+1,R[v],A[v]);
        }
        else{
            //query
            scan(v);
            printll(query(1,1,N,L[v],R[v]));
        }
    }
}

Second solution

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <string>
#include <cassert>

using namespace std;

#define all(X) (X).begin(), (X).end()

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

const int mod = 1e9 + 7;
const int maxn = 100001;

int tree[maxn << 4], lazy[maxn << 4];

int p(int base, int power) {
    int res = 1;
    while (power) {
        if (power & 1) res = res * 1LL * base % mod;
        power >>= 1;
        base = base * 1LL * base % mod;
    }
    return res;
}

int mul(int a, int b) {
    return a * 1LL * b % mod;
}

void init(int l, int r, int idx) {
    if (l == r) {
        tree[idx] = lazy[idx] = 1;
        return;
    }
    init(l, (l + r) / 2, idx << 1);
    init((l + r) / 2 + 1, r, (idx << 1) | 1);
    lazy[idx] = 1;
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

void relax(int node) {
    if (lazy[node] > 1) {
        tree[node] = mul(tree[node], lazy[node]);
        lazy[node << 1] = mul(lazy[node << 1], lazy[node]);
        lazy[(node << 1) | 1] = mul(lazy[(node << 1) | 1], lazy[node]);
        lazy[node] = 1;
    }
}

void update(int s, int e, int l, int r, int idx, int val) {
    relax(idx);
    if (r < s || l > e || l > r) return;
    if (s >= l && e <= r) {
        lazy[idx] = mul(lazy[idx], val);
        relax(idx);
        return;
    }
    update(s, (s + e) / 2, l, r, idx * 2, val);
    update((s + e) / 2 + 1, e, l, r, idx * 2 + 1, val);
    tree[idx] = (tree[idx * 2] + tree[idx * 2 + 1]) % mod;
}

int read(int s, int e, int l, int r, int idx) {
    relax(idx);
    if (r < s || l > e || l > r) return 0;
    if (s >= l && e <= r) return tree[idx];
    int res = read(s, (s + e) / 2, l, r, idx * 2);
    res += read((s + e) / 2 + 1, e, l, r, idx * 2 + 1);
    tree[idx] = (tree[idx * 2] + tree[idx * 2 + 1]) % mod;
    if (res >= mod) res -= mod;
    return res;
}

int st[maxn], ed[maxn], dis;
VI e[maxn];

void dfs(int u, int par) {
    st[u] = ++dis;
    for (auto v : e[u]) {
        if (v != par) dfs(v, u);
    }
    ed[u] = dis;
}

int A[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, Q, x, y, v, t;
    cin >> N >> Q;
    for (int i = 1; i < N; ++i) {
        cin >> x >> y;
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }
    init(1, N, 1);
    dfs(1, -1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        update(1, N, st[i] + 1, ed[i], 1, A[i]);
    }
    while (Q--) {
        cin >> t >> v;
        if (t == 1) {
            cin >> x;
            int upVal = x * 1LL * p(A[v], mod - 2) % mod;
            A[v] = x;
            update(1, N, st[v] + 1, ed[v], 1, upVal);
        } else {
            cout << read(1, N, st[v], ed[v], 1) << "n";
        }
    }
    return 0;
}

coding problems