Cerinta completa

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn’t require implementing any fancy techniques?

There are types of query operations that can be performed on a tree:

  1. 1 u x: Assign as the value of node .
  2. 2 u v: Print the sum of the node values in the unique path from node to node .

Given a tree with nodes where each node’s value is initially , execute queries.

Input Format

The first line contains space-separated integers, and , respectively.
The subsequent lines each contain space-separated integers describing an undirected edge in the tree.
Each of the subsequent lines contains a query you must execute.

Constraints

  • It is guaranteed that the input describes a connected tree with nodes.
  • Nodes are enumerated with -based indexing.

Output Format

For each type- query, print its integer result on a new line.

Sample Input

3 3
0 1
1 2
1 0 1
1 1 2
2 0 2

Sample Output

3

Explanation

After the first queries, the value of node and the value of node . The third query requires us to print the sum of the node values in the path from nodes to , which is . Thus, we print on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

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

vector<int> adj[N];
int n, q;

int tree[2*N];
vector<int> 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;
}

Scor obtinut: 1.0

Submission ID: 464655551

Link challenge: https://www.hackerrank.com/challenges/lazy-white-falcon/problem

Lazy White Falcon