5 years ago+ 1 comment

Hello. Please can anyone help me with this problem? I'm getting a timeout for the testcase with 100000 queries. I suspect the problem is from my algorithm to calculate the sum. The code is below:

int sumPath(Node* x, Node* y) {
    int sum = 0;
    // while x is on a level below y, ascend while adding the values to sum
    while (x->level > y->level) {
        sum += x->data;
        x = x->parent;
    }
    // while y is on a level below x, ascend while adding the values to sum
    while (y->level > x->level) {
        sum += y->data;
        y = y->parent;
    }
    //x and y are on the same level now.
    //ascend while their parents are not equal and add values to sum
    while (x != y) {
        sum += y->data;
        sum += x->data;
        x = x->parent;
        y = y->parent;
    }
    //x and y must be pointing to the same node now which is the lowest common anscestor.
    //Add the node's value to sum.
    return sum + x->data;
}

Is there a better way to implement it?

4 years ago+ 0 comments

include

using namespace std;

const int N = 100010; const int LG_N = 20;

vector adj[N]; int n, q;

int tree[2*N]; vector euler; int first[N], last[N];

int H[N], P[N][LG_N]; int val[N];

void dfs(int u, int p, int h) { H[u] = h; P[u][0] = p; for(int i = 1;i < LG_N;i++) { P[u][i] = P[P[u][i-1]][i-1]; } first[u] = euler.size(); euler.push_back(u); for(int v : adj[u]) { if(v == p) { continue; } dfs(v, u, h+1); } last[u] = euler.size(); euler.push_back(u); } int lca(int u, int v) { if(H[u] < H[v]) swap(u, v); for(int i = LG_N-1;i >= 0;i--) { if(H[P[u][i]] >= H[v]) { u = P[u][i]; }
} if(u == v) { return u; } for(int i = LG_N-1;i >= 0;i--) { if(P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } return P[u][0]; } void update(int idx, int val) { while(idx < euler.size()) { tree[idx] += val; idx += idx & (-idx); } } int query(int idx) { int ans = 0; while(idx > 0) { ans += tree[idx]; idx -= idx & (-idx); } return ans; } int main() {

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

euler.resize(1, 0);
dfs(0, 0, 0);

for(int i = 0;i < q;i++) {
    int type;
    cin >> type;
    if(type == 1) {
        int u, x;
        cin >> u >> x;
        update(first[u], x - val[u]);
        update(last[u],  val[u] - x);
        val[u] = x;
    }else {
        int u, v;
        cin >> u >> v;
        int l = lca(u, v);
        int ans = query(first[u]) + query(first[v]);
        ans = ans - 2 * query(first[l]) + val[l];
        cout << ans << "\n";
    }
}
return 0;

}

include

include

include

include

include

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge