本文共 4544 字，大约阅读时间需要 15 分钟。

为了解决这个问题，我们需要处理一棵树上的四种操作，每个操作都会对路径上的节点值进行加法或求和。为了高效处理这些操作，我们可以使用深度优先搜索（DFS）预处理和线段树来支持区间操作。

方法思路

解决代码

import syssys.setrecursionlimit(1 << 25)MOD = 10**18 + 3def main():    import sys    input = sys.stdin.read    data = input().split()    idx = 0    N = int(data[idx]); idx +=1    M = int(data[idx]); idx +=1    root = int(data[idx]); idx +=1    P = int(data[idx]); idx +=1    v = list(map(int, data[idx:idx+N]))    idx += N    v = [0] + v  # 1-based    edges = [[] for _ in range(N+1)]    for _ in range(N-1):        x = int(data[idx]); idx +=1        y = int(data[idx]); idx +=1        edges[x].append(y)        edges[y].append(x)    from collections import deque    # 预处理，计算sz, fa, son, d, top, id, rk    sz = [0]*(N+1)    fa = [0]*(N+1)    son = [0]*(N+1)    d = [0]*(N+1)    top = [0]*(N+1)    id = [0]*(N+1)    rk = [0]*(N+1)    time = 0    visited = [False]*(N+1)    stack = [(root, -1)]    while stack:        x, parent = stack.pop()        if visited[x]:            continue        visited[x] = True        sz[x] = 1        for child in edges[x]:            if child != parent and not visited[child]:                fa[child] = x                son[x] = child                stack.append((child, x))        sz[x] = sum(sz[child] for child in edges[x] if child != parent and fa[child] == x)    # 预处理top, id, rk    top[root] = root    id[root] = 1    rk[1] = root    time = 2    stack = [(root, root)]    while stack:        x, p = stack.pop()        for child in edges[x]:            if child != p and fa[child] == x:                top[child] = top[x]                id[child] = time                rk[time] = child                time +=1                stack.append((child, x))    # 线段树构建    # 非动态开点，线段树大小为 2*2^h, 其中 h 是最小使得 2^h >= N    maxn = 2 * (1 << (20 if N > 100000 else 17))    a = [0]*(2*maxn)    for i in range(1, N+1):        a[id[i]] = v[i]    for i in range(maxn-1, 0, -1):        a[i] = (a[2*i] + a[2*i+1]) % P    def update(l, r, val, node):        if l == r:            a[node] = (a[node] + val * (r - l +1)) % P            return        mid = (l + r) //2        if l <= mid:            update(l, mid, val, 2*node)        if r > mid:            update(mid+1, r, val, 2*node+1)        a[node] = (a[2*node] + a[2*node+1]) % P    def query(l, r, node):        if l > r:            return 0        if l == r:            return a[node]        mid = (l + r) //2        res = 0        if l <= mid:            res += query(l, mid, 2*node)        if r > mid:            res += query(mid+1, r, 2*node+1)        return res % P    for _ in range(M):        parts = data[idx:idx+4]        if parts[0] == '1':            x = int(data[idx+1])            y = int(data[idx+2])            z = int(data[idx+3])            idx +=4            while top[x] != top[y]:                if d[top[x]] > d[top[y]]:                    x, y = y, x                start = id[top[x]]                end = id[x]                update(start, end, z, 1)                x = fa[top[x]]            if top[x] == top[y]:                x = y            start = id[x]            end = id[x]            update(start, end, z, 1)        elif parts[0] == '2':            x = int(data[idx+1])            y = int(data[idx+2])            idx +=3            res = 0            while top[x] != top[y]:                if d[top[x]] > d[top[y]]:                    x, y = y, x                start = id[top[x]]                end = id[x]                res += query(start, end, 1)                res %= P                x = fa[top[x]]            if top[x] == top[y]:                x = y            start = id[x]            end = id[x]            res += query(start, end, 1)            res %= P            print(res % P)        elif parts[0] == '3':            x = int(data[idx+1])            z = int(data[idx+2])            idx +=3            start = id[x]            end = rk[x]            update(start, end, z, 1)        elif parts[0] == '4':            x = int(data[idx+1])            idx +=2            start = id[x]            end = rk[x]            res = query(start, end, 1)            print(res % P)if __name__ == '__main__':    main()

代码解释

这种方法确保了路径和子树操作的高效处理，适用于大规模数据。

转载地址：http://cnzv.baihongyu.com/