Illusions of the Desert (Codeforces 1575I)
Tags: Others, trees

Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.The map of the labyrinth forms a tree with $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$ and $$$n - 1$$$ tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.The $$$i$$$-th room ($$$1 \leq i \leq n$$$) has $$$a_i$$$ illusion rate. To go from the $$$x$$$-th room to the $$$y$$$-th room, there must exist a tunnel between $$$x$$$ and $$$y$$$, and it takes $$$\max(|a_x + a_y|, |a_x - a_y|)$$$ energy. $$$|z|$$$ denotes the absolute value of $$$z$$$.To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask $$$q$$$ queries.There are two types of queries to be done:  $$$1\ u\ c$$$ — The illusion rate of the $$$x$$$-th room is changed to $$$c$$$ ($$$1 \leq u \leq n$$$, $$$0 \leq |c| \leq 10^9$$$).  $$$2\ u\ v$$$ — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room $$$v$$$ if they are initially at room $$$u$$$ ($$$1 \leq u, v \leq n$$$). Help them, so you can get a portion of the treasure!

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of rooms in the maze and the number of queries.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq 10^9$$$) — inital illusion rate of each room.The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \leq s_i, t_i \leq n$$$), meaning there is a tunnel connecting $$$s_i$$$-th room and $$$t_i$$$-th room. The given edges form a tree.The next $$$q$$$ lines contain the query as described. The given queries are valid.

Output: For each type $$$2$$$ query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.

Note:   In the first query, their movement from the $$$1$$$-st to the $$$2$$$-nd room is as follows.  $$$1 \rightarrow 5$$$ — takes $$$\max(|10 + 4|, |10 - 4|) = 14$$$ energy.  $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.  $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ energy.  In total, it takes $$$39$$$ energy.In the second query, the illusion rate of the $$$1$$$-st room changes from $$$10$$$ to $$$-3$$$.In the third query, their movement from the $$$1$$$-st to the $$$2$$$-nd room is as follows.  $$$1 \rightarrow 5$$$ — takes $$$\max(|-3 + 4|, |-3 - 4|) = 7$$$ energy.  $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.  $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ energy. Now, it takes $$$32$$$ energy.

Sample Inputs:
6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3

Sample Outputs:
39
32
0

Solution (Python):
def naiveSolve():
    return

def solve():
    return
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    for i in range(n):
        a[i] = abs(a[i])
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readIntArr()
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    root = 0

    @bootstrap
    def eulerTour(node, p):
        up[node][0] = p
        tin[node] = time[0]
        eulerTourArr[time[0]] = 2 * a[node]
        time[0] += 1
        for v in adj[node]:
            if v != p:
                yield eulerTour(v, node)
        tout[node] = time[0]
        eulerTourArr[time[0]] = -2 * a[node]
        time[0] += 1
        yield None
    time = [0]
    tin = [-1] * n
    tout = [-1] * n
    maxPow = 0
    while pow(2, maxPow) < n:
        maxPow += 1
    maxPow += 1
    up = [[-1 for _ in range(maxPow)] for __ in range(n + 1)]
    eulerTourArr = [0] * (2 * n)
    eulerTour(root, -1)
    for i in range(1, maxPow):
        for u in range(1, n + 1):
            if up[u][i - 1] == -1 or up[up[u][i - 1]][i - 1] == -1:
                continue
            up[u][i] = up[up[u][i - 1]][i - 1]

    def isAncestor(u, v):
        return tin[u] <= tin[v] and tout[u] >= tout[v]

    def findLCA(u, v):
        if not isAncestor(u, v):
            u2 = u
            for i in range(maxPow - 1, -1, -1):
                if up[u2][i] != -1 and (not isAncestor(up[u2][i], v)):
                    u2 = up[u2][i]
            lca = up[u2][0]
        else:
            lca = u
        return lca
    st = getSumSegTree(eulerTourArr)
    allans = []
    for _ in range(q):
        (x, u, v) = readIntArr()
        u -= 1
        if x == 1:
            c = abs(v)
            st.update(tin[u], 2 * c)
            st.update(tout[u], -2 * c)
            a[u] = c
        else:
            v -= 1
            rootToU = st.query(0, tin[u]) - a[root] - a[u]
            rootToV = st.query(0, tin[v]) - a[root] - a[v]
            lca = findLCA(u, v)
            rootToLCA = st.query(0, tin[lca]) - a[root] - a[lca]
            ans = rootToU + rootToV - 2 * rootToLCA
            allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
    print('{}'.format(x))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
    main()

Solution (Python):
def naiveSolve():
    return

def solve():
    return
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readIntArr()
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    root = 0

    @bootstrap
    def eulerTour(node, p):
        up[node][0] = p
        tin[node] = time[0]
        eulerTourArr[time[0]] = 2 * abs(a[node])
        time[0] += 1
        for v in adj[node]:
            if v != p:
                yield eulerTour(v, node)
        tout[node] = time[0]
        eulerTourArr[time[0]] = -2 * abs(a[node])
        time[0] += 1
        yield None
    time = [0]
    tin = [-1] * n
    tout = [-1] * n
    maxPow = 0
    while pow(2, maxPow) < n:
        maxPow += 1
    maxPow += 1
    up = [[-1 for _ in range(maxPow)] for __ in range(n + 1)]
    eulerTourArr = [0] * (2 * n)
    eulerTour(root, -1)
    for i in range(1, maxPow):
        for u in range(1, n + 1):
            if up[u][i - 1] == -1 or up[up[u][i - 1]][i - 1] == -1:
                continue
            up[u][i] = up[up[u][i - 1]][i - 1]

    def isAncestor(u, v):
        return tin[u] <= tin[v] and tout[u] >= tout[v]

    def findLCA(u, v):
        if not isAncestor(u, v):
            u2 = u
            for i in range(maxPow - 1, -1, -1):
                if up[u2][i] != -1 and (not isAncestor(up[u2][i], v)):
                    u2 = up[u2][i]
            lca = up[u2][0]
        else:
            lca = u
        return lca
    st = getSumSegTree(eulerTourArr)
    allans = []
    for _ in range(q):
        (x, u, v) = readIntArr()
        u -= 1
        if x == 1:
            c = v
            st.update(tin[u], 2 * abs(c))
            st.update(tout[u], -2 * abs(c))
            a[u] = c
        else:
            v -= 1
            rootToU = st.query(0, tin[u]) - abs(a[root]) - abs(a[u])
            rootToV = st.query(0, tin[v]) - abs(a[root]) - abs(a[v])
            lca = findLCA(u, v)
            rootToLCA = st.query(0, tin[lca]) - abs(a[root]) - abs(a[lca])
            ans = rootToU + rootToV - 2 * rootToLCA
            allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
    print('{}'.format(x))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
    main()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
INF = float('inf')

class lca_binarylift(object):

    def __init__(self, neigh):
        set_root = 0
        self.n = len(neigh)
        self.parents = [[] for i in range(self.n)]
        self.depth = [-1] * self.n
        self.depth[set_root] = 0
        self.parents[set_root].append(-1)
        queue = deque([[set_root, 0]])
        while queue:
            (index, d) = queue.popleft()
            for nextindex in neigh[index]:
                if self.depth[nextindex] >= 0:
                    continue
                self.depth[nextindex] = d + 1
                self.parents[nextindex].append(index)
                queue.append([nextindex, d + 1])
        self.maxdepth = max(self.depth)
        k = 1
        while True:
            op = 0
            for i in range(self.n):
                if len(self.parents[i]) == k and self.parents[i][k - 1] >= 0:
                    nextl = len(self.parents[self.parents[i][k - 1]])
                    actual = min(nextl - 1, k - 1)
                    self.parents[i].append(self.parents[self.parents[i][k - 1]][actual])
                    op += 1
            if op == 0:
                break
            k += 1

    def move(self, index, step):
        if step > self.depth[index]:
            return -1
        i = 0
        while step:
            if step & 1:
                index = self.parents[index][i]
            step = step >> 1
            i += 1
        return index

    def query(self, index1, index2):
        if self.depth[index1] >= self.depth[index2]:
            index1 = self.move(index1, self.depth[index1] - self.depth[index2])
        else:
            index2 = self.move(index2, self.depth[index2] - self.depth[index1])
        front = 0
        rear = self.maxdepth + 1
        while front < rear:
            mid = (front + rear) // 2
            if self.move(index1, mid) == self.move(index2, mid):
                rear = mid
            else:
                front = mid + 1
        return self.move(index1, front)

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

    def query(self, front, rear):
        return self.getaccu(rear) - self.getaccu(front - 1)

class heavy_light(object):

    def __init__(self, n, neigh):
        self.n = n
        self.children = [[] for i in range(n)]
        self.neigh = neigh
        self.parent = [-1] * n
        self.ancestor = [-1] * n
        self.rename = [-1] * n
        self.totnum = [0] * n
        self.maxchild = [-1] * n
        self.renameindex()

    def getchild(self):
        visited = [False] * self.n
        queue = deque()
        queue.append(0)
        visited[0] = True
        seq = [0]
        while queue:
            index = queue.popleft()
            for nextindex in self.neigh[index]:
                if visited[nextindex]:
                    continue
                visited[nextindex] = True
                queue.append(nextindex)
                self.children[index].append(nextindex)
                self.parent[nextindex] = index
                seq.append(nextindex)
        for index in seq[::-1]:
            maxcnum = 0
            for ele in self.children[index]:
                self.totnum[index] += self.totnum[ele]
                if self.totnum[ele] > maxcnum:
                    maxcnum = self.totnum[ele]
                    self.maxchild[index] = ele
            self.totnum[index] += 1

    def renameindex(self):
        self.getchild()
        stack = [(0, 0)]
        currindex = 0
        while stack:
            (index, ances) = stack.pop()
            for ele in self.children[index]:
                if ele == self.maxchild[index]:
                    continue
                stack.append((ele, ele))
            self.ancestor[index] = ances
            self.rename[index] = currindex
            if self.maxchild[index] > 0:
                stack.append((self.maxchild[index], ances))
            currindex += 1

    def getpath(self, index):
        output = []
        ori = index
        while index >= 0:
            front = self.rename[self.ancestor[index]]
            rear = self.rename[index]
            output.append([front, rear])
            index = self.parent[self.ancestor[index]]
        return output[::-1]
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
    arr[i] = abs(arr[i])
neigh = [[] for i in range(n)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    neigh[u - 1].append(v - 1)
    neigh[v - 1].append(u - 1)
new = heavy_light(n, neigh)
lca = lca_binarylift(neigh)
fen = fenwick(n)
for i in range(n):
    index = new.rename[i]
    fen.update(index, arr[i])
for _ in range(q):
    (op, a, b) = map(int, input().split())
    if op == 1:
        i = a - 1
        index = new.rename[i]
        diff = abs(b) - arr[i]
        arr[i] = abs(b)
        fen.update(index, diff)
    else:
        (front, rear) = (a - 1, b - 1)
        oricommon = lca.query(a - 1, b - 1)
        to_rear = new.getpath(b - 1)
        to_front = new.getpath(a - 1)
        to_common = new.getpath(oricommon)
        output = 0
        for ele in to_rear:
            output += fen.query(ele[0], ele[1])
        for ele in to_front:
            output += fen.query(ele[0], ele[1])
        for ele in to_common:
            output -= 2 * fen.query(ele[0], ele[1])
        output += arr[oricommon]
        output = 2 * output - arr[front] - arr[rear]
        print(output)