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

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

方法思路

解决代码

import sys
sys.setrecursionlimit(1 << 25)
MOD = 10**18 + 3
def 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/