Algorithms

树

• 满二叉树
• dfs求两点距离
• DFS求每个点的高度
• 倍增求LCA
• Tarjan求LCA
• 题目描述
• 输入格式
• 输出格式
  • 树上差分
  • 根据每条边两边的点的情况，计算边的贡献的dfs
    • CF1401D
    • 2017 ICPC 沈阳 Tree
    • 2019 CCPC 威海 C
  • 树的直径
    • 两次dfs
    • 树形DP
  • 树的中心
  • 树的重心
    • 定义
    • 根据定义求树的重心
    • 性质
    • 求所有子树的重心（徐州ICPC2019）
    • cf1406c：把有两个重心的树变成一个重心
  • 启发式合并
  • 树链剖分
    • 定义
    • 将树从x到y结点最短路径上所有节点的值都加上z
    • 求树从x到y结点最短路径上所有节点的值之和
    • 洛谷P3384

满二叉树

节点个数必为奇数个

香港icpc2019

给定一棵树，两个人轮流进行游戏，一个人每次能从树上取走一棵符合满二叉树性质的子树，询问谁能必胜。

解：满二叉树节点个数必为奇数个。故节点个数为奇数时先手必胜，否则后手必胜。

#include <cstdio>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n - 1; ++i) scanf("%*d%*d");
        puts(n & 1 ? "Alice" : "Bob");
    }
    return 0;
}

dfs求两点距离

int dis;
void get_dis(int cur, int end, int father, int depth) {
    if (cur == end) {
        dis = depth;
        return;
    }
    for (auto i : tree[cur]) {
        if (i != father) {
            get_dis(i, end, cur, depth + 1);
        }
    }
}

DFS求每个点的高度

int height[1000006];

void get_height(int cur, int depth) {
    if (sons[cur].empty()) {
        height[cur] = 0;
        return;
    }
    int h = 0;
    for (auto &i : sons[cur]) {
        get_height(i, depth + 1);
        h = std::max(h, height[i]);
    }
    height[cur] = h + 1;
}

倍增求LCA

/**
 * luogu3379
 */

#include <cstdio>
#include <algorithm>

using namespace std;

struct Edge {
    int v;
    int next;
} edges[500002 << 1];
int heads[500002];
int total = 0;

int depth[500002] = {0};
int ancestors[500002][22] = {0};

int LOG_2[500002];

void add_edge(int u, int v) {
    edges[++total] = {v, heads[u]};
    heads[u] = total;
}

void dfs(int cur_v, int parent) {
    ancestors[cur_v][0] = parent;
    depth[cur_v] = depth[parent] + 1;

    for (int i = 1; i <= LOG_2[depth[cur_v]]; ++i) {
        ancestors[cur_v][i] = ancestors[ancestors[cur_v][i-1]][i-1];
    }

    for (int i = heads[cur_v]; i; i = edges[i].next) {
        if (edges[i].v != parent) {
            dfs(edges[i].v, cur_v);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    while (depth[a] > depth[b]) {
        a = ancestors[a][LOG_2[depth[a]-depth[b]]];
    }
    if (a == b) {
        return a;
    }
    for (int i = LOG_2[depth[a]]; i >= 0; --i) {
        if (ancestors[a][i] != ancestors[b][i]) {
            a = ancestors[a][i];
            b = ancestors[b][i];
        }
    }
    return ancestors[a][0];
}

void get_log_2() {
    LOG_2[1] = 0;
    for (int i = 2; i <= 500001; ++i) {
        LOG_2[i] = LOG_2[i>>1] + 1;
    }
}

int main() {
    get_log_2();

    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);

    int x, y;
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d %d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }

    dfs(s, 0);

    int a, b;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }

    return 0;
}

Tarjan求LCA

Tarjan算法求LCA的本质是用并查集对向上标记法进行优化，是一种离线算法，时间复杂度 $$O(n+m)$$

求LCA的Tarjan算法主体由dfs实现，并用并查集进行优化。对于每个节点，我们增加一个标记：

• 若该节点没有访问过，则初值为0
• 若该节点已访问但还没有回溯，则标记为1
• 若该节点已访问且已回溯，则标记为2

显然，对于当前访问的节点 x，它到根节点的路径一定都被标记为1。因此对于任意一个与 x相关的询问，设询问的另一个节点为 y，则 LCA(x,y)即为 y到根节点的路径中第一个，也就是最深的标记为1的节点。

求这个节点的方法可以用并查集优化。当一个节点的标记改为2的同时，将它合并到其父节点的集合当中。显然，此时它的父节点的标记一定为1，并且单独构成一个集合，因为这个父节点还没有进行过回溯操作。

在合并过后，遍历关于当前节点 x的所有询问，对于任意一个询问，若 y的标记为2，说明其已经被访问过，并且它的并查集指向的那个节点，也就是 y到根节点的路径中最深的还没有回溯的节点，一定就是 LCA(x,y)。

对于询问，我们可以用一个不定长数组存储与每个节点相关的询问，并且每个询问用一个二元组表示，第一维存储该询问的另一个节点，第二维存储该询问输入的次序，以便按顺序输出

这样，Tarjan算法求LCA的步骤就很明了了：

1. 从根节点开始进行dfs

2. 将当前节点标记为1

3. 遍历当前节点的所有出边；若当前边的终点还没有访问过，则访问它，访问过后将该节点合并到当前节点的集合中；

4. 遍历与当前节点相关的所有询问；若当前询问的另一个节点的标记为2，则该询问的答案即为另一个节点所在集合的代表元素

5. 将当前节点标记为2

   题目描述

   如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

   输入格式

   第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

   接下来 N-1 行每行包含两个正整数 x, y，表示 xx 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。

   接下来 M 行每行包含两个正整数 a, b，表示询问 a结点和 b 结点的最近公共祖先。

   输出格式

   输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

/* input
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
*/

/* output
4
4
1
4
4
*/

// 
// Created by Jiang Yinzuo on 2020/10/28.
// Tarjan Algorithm O(n + m)

#include <cstdio>
#include <vector>

constexpr int MAX_N = 500000;
constexpr int MAX_M = 500000;
std::vector<int> tree[MAX_N + 1];
/// queries[x] = {y, id}
std::vector<std::pair<int, int> > queries[MAX_N];

///// Union Find /////
int father[MAX_N + 1];

int get_father(int v) {
    return father[v] == v ? v : father[v] = get_father(father[v]);
}

int answer[MAX_M + 1];

void tarjan(int cur_v) {
    static int tag[MAX_N + 1] = {0};
    tag[cur_v] = 1;
    for (auto i : tree[cur_v]) {
        if (tag[i] == 0) {
            tarjan(i);
            father[i] = cur_v; // merge child vertex to self
        }
    }
    for (auto &q : queries[cur_v]) {
        int y = q.first, id = q.second;
        if (tag[y] == 2) answer[id] = get_father(y);
    }
    tag[cur_v] = 2;
}

int main() {
    int n, m, root;
    scanf("%d %d %d", &n, &m, &root);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        queries[a].emplace_back(b, i);
        queries[b].emplace_back(a, i);
    }

    for (int i = 0; i <= n; ++i) father[i] = i;

    tarjan(root);
    for (int i = 0; i < m; ++i) printf("%d\n", answer[i]);
    return 0;
}

树上差分

根据每条边两边的点的情况，计算边的贡献的dfs

CF1401D

2017 ICPC 沈阳 Tree

2019 CCPC 威海 C

给一棵带边权的树$$<E, V, W>$$，给3个树上的点集$$V_1, V_2, V_3 \subseteq V$$。记$$v_1 \in V_1, v_2 \in V_2, v_3 \in V_3$$，求$$\mathbb{E}[{f(v_1, v_2, v_3)}]$$。$$f(v_1, v_2, v_3) = \min \limits_{v \in V}(\sum_{i=1}^3 distance(v_i, v))$$

解：观察得，$$f(v_1, v_2, v_3) = \frac{1}{2}(distance(v_1, v_2) + distance(v_2, v_3) + distance(v_3, v_1))$$

故 $$ \mathbb{E}[{f(v_1, v_2, v_3)}] = \mathbb{E}[\frac{1}{2}(distance(v_1, v_2) + distance(v_2, v_3) + distance(v_3, v_1))] \ = \frac{1}{2}( \mathbb{E}[distance(v_1, v_2)] + \mathbb{E}[distance(v_2, v_3)] + \mathbb{E}[distance(v_1, v_3)]) $$ 对一棵树，计算每条边的贡献：一条边的两侧分别有多少个$$v_1, v_2, v_3$$

#include <cstdio>
#include <vector>

constexpr int MAX_N = 200001;
struct Vertex {
    int to;
    unsigned long long weight;
};
std::vector<Vertex> tree[MAX_N];
long long sci_cnt[3][MAX_N] = {0};
long long tot_cnt[3];
bool has[3][MAX_N] = {false};

unsigned long long ans[3] = {0};

void dfs(int cur_v, int father, unsigned long long fa_cur_weight) {
    for (int i = 0; i < 3; ++i) {
        sci_cnt[i][cur_v] += has[i][cur_v];
    }
    for (auto &v : tree[cur_v]) {
        if (v.to != father) {
            dfs(v.to, cur_v, v.weight);
            for (int i = 0; i < 3; ++i) {
                sci_cnt[i][cur_v] += sci_cnt[i][v.to];
            }
        }
    }
    for (int i = 0; i < 3; ++i) {
        ans[i] += fa_cur_weight * (sci_cnt[i][cur_v] *
                                   (tot_cnt[(i + 1) % 3] - sci_cnt[(i + 1) % 3][cur_v]) +
                                   sci_cnt[(i + 1) % 3][cur_v] * (tot_cnt[i] - sci_cnt[i][cur_v]));
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        unsigned long long w;
        scanf("%d %d %llu", &u, &v, &w);
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }
    int i = 0;
    for (auto &ha : has) {
        int plc;
        scanf("%d", &tot_cnt[i]);
        for (int j = 0; j < tot_cnt[i]; ++j) {
            scanf("%d", &plc);
            ha[plc] = true;
        }
        ++i;
    }
    dfs(1, 0, 0);
    double answer = 0;
    for (i = 0; i < 3; ++i) {
        answer += ans[i] / (double )(tot_cnt[i] * tot_cnt[(i+1)%3]);
    }
    printf("%.12lf\n", answer / (double )2);
    return 0;
}

树的直径

两次dfs

先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径

int max_depth = 0;
int end1;
void get_diameter(int cur, int father, int depth) {
    if (tree[cur].size() == 1 && father != -1 && depth > max_depth) {
        max_depth = depth;
        end1 = cur;
    }
    for (auto i : tree[cur]) {
        if (i != father) {
            get_diameter(i, cur, depth + 1);
        }
    }
}

int main() {
    max_depth = 0;
    get_diameter(1, -1, 1);
    get_diameter(end1, -1, 1);
    int diameter = max_depth;
    return 0;
}

树形DP

树的中心

树的直径的中点称为树的中心。以树的中心为整棵树的根时，从该根到每个叶子节点的最长路径最短

例题：给一棵树（n个点），求最少移去几个点，使得剩下的图仍然构成一棵树，且直径为k

解：设直径为D。

k为偶数时，一棵树上存在一点V使得树上任意一点到V的距离小于等于D/2。

k为奇数时，存在一条边E使得树上任意一点到E的其中一个端点距离小于等于$\lfloor D/2 \rfloor$

故只需枚举点V或者边E，dfs求出距离小于等于D/2的点的个数，并维护最大值即可。

//
// Created by Jiang Yinzuo on 2020/12/11.
//

#include <cstdio>
#include <vector>

constexpr int MaxN = 2001;

std::vector<int> tree[MaxN];
std::vector<std::pair<int, int>> edges;

int ans;
void dfs(int cur_v, int father, int depth, const int max_depth) {
    if (depth > max_depth) {
        return;
    }
    --ans;
    for (auto i : tree[cur_v]) {
        if (i != father) {
            dfs(i, cur_v, depth + 1, max_depth);
        }
    }
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
        (void)edges.emplace_back(u, v);
    }

    int min_ans = n;
    if (k % 2 == 0) {
        for (int i = 1; i <= n; ++i) {
            ans = n;
            dfs(i, 0, 0, k / 2);
            min_ans = min_ans < ans ? min_ans : ans;
        }
    } else {
        for (auto &p : edges) {
            ans = n;
            dfs(p.first, p.second, 0, k / 2);
            dfs(p.second, p.first, 0, k / 2);
            min_ans = min_ans < ans ? min_ans : ans;
        }
    }

    printf("%d\n", min_ans);
    return 0;
}

树的重心

定义

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

（这里以及下文中的“子树”都是指无根树的子树，即包括“向上”的那棵子树，并且不包括整棵树自身。）

根据定义求树的重心

//
// Created by jiang on 2020/8/15.
// poj1655

#include <cstdio>
#include <vector>

std::vector<int> tree[200001];
int size[200001];
int max_size[200001];
int n;
int centroid, min_max_size = 0x7fffffff;

void dfs(int cur_v, int father) {
    size[cur_v] = max_size[cur_v] = 1;
    for (auto &i : tree[cur_v]) {
        if (i != father) {
            dfs(i, cur_v);
            size[cur_v] += size[i];
            max_size[cur_v] = std::max(max_size[cur_v], size[i]);
        }
    }
    max_size[cur_v] = std::max(max_size[cur_v], n - size[cur_v]);
    if (min_max_size > max_size[cur_v]) {
        centroid = cur_v;
        min_max_size = max_size[cur_v];
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int u, v;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) tree[i].clear();
        for (int i = 0; i < n - 1; ++i) {
            scanf("%d %d", &u, &v);
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        min_max_size = 0x7fffffff;
        dfs(1, 0);
        printf("%d %d\n", centroid, min_max_size);
    }
    return 0;
}

性质

1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
3. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
5. 一棵树最多有两个重心，且这两个重心相邻。

求所有子树的重心（徐州ICPC2019）

//
// Created by jiang on 2020/8/15.
// https://nanti.jisuanke.com/t/42552

#include <cstdio>
#include <vector>

#define MAXN 200001
std::vector<int> tree[MAXN];

/**
 * fathers: 每个节点的父亲
 * depth： 每个节点的深度
 * centroids: 每个子树深度较深的重心
 * size: 每个子树的节点数量
 */
int fathers[MAXN], depth[MAXN], centroids[MAXN], size[MAXN];

/**
 * 合并两棵子树的重心时，新的重心一定在子树重心的连线上
 * @param cur_v 合并后的根节点
 * @param c1 子树1的重心
 * @param c2 子树2的重心
 */
void merge(int cur_v, int c1, int c2) {
    while (depth[c1] > depth[cur_v] && size[c1] < size[cur_v] - size[c1])
        c1 = fathers[c1];
    while (depth[c2] > depth[cur_v] && size[c2] < size[cur_v] - size[c2])
        c2 = fathers[c2];
    centroids[cur_v] = depth[c1] > depth[c2] ? c1 : c2;
}

void dfs(int cur_v) {
    size[cur_v] = 1;
    centroids[cur_v] = cur_v;
    for (auto &i : tree[cur_v]) {
        if (i != fathers[cur_v]) {
            fathers[i] = cur_v;
            depth[i] = depth[cur_v] + 1;
            dfs(i);
            size[cur_v] += size[i];
            merge(cur_v, centroids[cur_v], centroids[i]);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int u, v;
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d %d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    fathers[1] = 0;
    depth[1] = 1;
    dfs(1);

    // 一棵树最多2个重心
    for (int i = 1; i <= n; ++i) {
        if (fathers[centroids[i]] && size[centroids[i]] * 2 == size[i]) {
            if (centroids[i] < fathers[centroids[i]])
                printf("%d %d\n", centroids[i], fathers[centroids[i]]);
            else
                printf("%d %d\n", fathers[centroids[i]], centroids[i]);
        } else {
            printf("%d\n", centroids[i]);
        }
    }
    return 0;
}

cf1406c：把有两个重心的树变成一个重心

找到一个重心的一边的叶子节点，和另一个重心相连。

//
// Created by jiang on 2020/9/17.
// 求树的重心

#include <cstdio>
#include <vector>

std::vector<int> tree[200001];
int size[200001];
int max_size[200001];
int n;
std::vector<int> centroids;
int min_max_size;

void dfs(int cur_v, int father) {
    size[cur_v] = max_size[cur_v] = 1;
    for (auto &i : tree[cur_v]) {
        if (i != father) {
            dfs(i, cur_v);
            size[cur_v] += size[i];
            max_size[cur_v] = std::max(max_size[cur_v], size[i]);
        }
    }
    max_size[cur_v] = std::max(max_size[cur_v], n - size[cur_v]);
    if (min_max_size >= max_size[cur_v]) {
        if (min_max_size > max_size[cur_v]) centroids.clear();
        centroids.push_back(cur_v);
        min_max_size = max_size[cur_v];
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int u, v;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) tree[i].clear();
        for (int i = 0; i < n - 1; ++i) {
            scanf("%d %d", &u, &v);
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        min_max_size = 0x7fffffff;
        dfs(1, 0);
        if (centroids.size() == 1) {
            printf("%d %d\n", tree[1][0], 1);
            printf("%d %d\n", tree[1][0], 1);
        } else {
            int c1 = centroids[0], c2 = centroids[1];
            int child, cur = c1, father = c2;
            while (tree[cur].size() > 1) {
                for (int i = 0; (child = tree[cur][i]) == father; ++i);
                father = cur;
                cur = child;
            }
            printf("%d %d\n", cur, father);
            printf("%d %d\n", cur, c2);
        }
    }
    return 0;
}

启发式合并

洛谷U41492：树上每个节点有一个颜色，求任意子树的颜色数量。

如果给每个子树记录颜色，可能会超内存。因此需要将轻儿子的颜色合并到重儿子上。

//
// Created by Jiang Yinzuo on 2020/12/7.
//

#include <cstdio>
#include <unordered_set>
#include <vector>

std::vector<int> tree[100001];
int color[100001];

int heavy_child[100001];
int size[100001];

/*
 * 求重儿子
 */
void dfs1(int cur_v, int father) {

    size[cur_v] = 1;
    int max_size = 0, heaviest_child = 0;
    for (auto &i : tree[cur_v]) {
        if (i != father) {
            dfs1(i, cur_v);
            size[cur_v] += size[i];
            if (size[i] > max_size) {
                max_size = size[i];
                heaviest_child = i;
            }
        }
    }
    heavy_child[cur_v] = heaviest_child;
}

int color_cnt[100001];

std::unordered_set<int> dfs2(int cur_v, int father) {
    if (tree[cur_v].size() == 1 && father != 0) {
        std::unordered_set<int> exist;
        color_cnt[cur_v] = 1;
        exist.insert(color[cur_v]);
        return exist;
    }

    auto heavy_exist = dfs2(heavy_child[cur_v], cur_v);
    for (auto &i : tree[cur_v]) {
        if (i != father && i != heavy_child[cur_v]) {
            auto light_exist = dfs2(i, cur_v);
            heavy_exist.merge(light_exist);
        }
    }

    heavy_exist.insert(color[cur_v]);
    color_cnt[cur_v] = heavy_exist.size();
    return heavy_exist;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", color + i);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        int q;
        scanf("%d", &q);
        printf("%d\n", color_cnt[q]);
    }
    return 0;
}

树链剖分

定义

1.重儿子：一个节点的儿子节点里面，以重儿子为根的子树大小最大。

2.轻儿子：一个节点的儿子节点，除了唯一一个重儿子，其余儿子为轻儿子。

3.重边：连接父亲和重儿子的边称为重边。

4.轻边：连接父亲和轻儿子的边称为轻边。

5.重链：只由重边构成的链称为重链。

将树从x到y结点最短路径上所有节点的值都加上z

树上差分O(n+m)

求树从x到y结点最短路径上所有节点的值之和

LCA：dfs O(n)预处理每个节点的dis（即到根节点的最短路径长度）

然后对于每个询问，求出x,y两点的lca，利用lca的性质distance ( x , y ) = dis ( x ) + dis ( y ) - 2 * dis ( lca )求出结果

时间复杂度O(mlogn+n)

洛谷P3384

题目描述

如题，已知一棵包含 N* 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作 1： 格式： 1 x y z 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。

操作 2： 格式： 2 x y 表示求树从 x 到 y 结点最短路径上所有节点的值之和。

操作 3： 格式： 3 x z 表示将以 x为根节点的子树内所有节点值都加上 z。

操作 4： 格式： 4 x 表示求以 x为根节点的子树内所有节点值之和

输入格式

第一行包含 44 个正整数 N,M,R,P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含 N 个非负整数，分别依次表示各个节点上初始的数值。

接下来 N-1 行每行包含两个整数 x,y，表示点 x和点 y之间连有一条边（保证无环且连通）。

接下来 M行每行包含若干个正整数，每行表示一个操作，格式如下：

操作 1： 1 x y z；

操作 2： 2 x y；

操作 3： 3 x z；

操作 4： 4 x。

输出格式

输出包含若干行，分别依次表示每个操作 2 或操作 4所得的结果（对 P 取模）。

//
// Created by Jiang Yinzuo on 2020/10/28.
//

#include <cstdio>
#include <vector>

constexpr int MAX_N = 200004;

std::vector<int> tree[MAX_N + 1];

////////////// tree split
int father[MAX_N];
int depth[MAX_N];
int size[MAX_N];
int heavy_son[MAX_N] = {0};
int chain_top[MAX_N]; // chain_top[v] =  top of the heavy chain containing v
int dfn[MAX_N], dfn_cnt = 0; // dfs order
int rank[MAX_N]; // rank[dfn[v]] = v

int weight[MAX_N];
int w[MAX_N];

/// process father, depth, size and heavy_son
void dfs1(int cur_v, int fa, int dep) {
    father[cur_v] = fa;
    depth[cur_v] = dep;
    size[cur_v] = 1;
    for (auto i : tree[cur_v]) {
        if (i != fa) {
            dfs1(i, cur_v, dep + 1);
            size[cur_v] += size[i];
            if (size[i] >= size[heavy_son[cur_v]]) {
                heavy_son[cur_v] = i;
            }
        }
    }
}

void dfs2(int cur_v, int top) {
    chain_top[cur_v] = top;
    dfn[cur_v] = ++dfn_cnt;
    weight[dfn_cnt] = w[cur_v];
    rank[dfn_cnt] = cur_v;
    if (!heavy_son[cur_v]) return;
    dfs2(heavy_son[cur_v], top);

    for (auto i : tree[cur_v]) {
        if (i != heavy_son[cur_v] && i != father[cur_v]) {
            dfs2(i, i); // top of a heavy chain
        }
    }
}
///////////////////

///// segment tree
int arr[(MAX_N << 2) + 1], lazy_tag[(MAX_N << 2) + 1] = {0};
int mod;

void push_down(int cur_v, int len) {
    lazy_tag[cur_v << 1] += lazy_tag[cur_v];
    lazy_tag[cur_v << 1 | 1] += lazy_tag[cur_v];
    arr[cur_v << 1] += lazy_tag[cur_v] * (len - (len >> 1));
    arr[cur_v << 1 | 1] += lazy_tag[cur_v] * (len >> 1);
    arr[cur_v << 1] %= mod;
    arr[cur_v << 1 | 1] %= mod;
    lazy_tag[cur_v] = 0;
}

void build(int cur_v, int l, int r) {
    if (l == r) {
        arr[cur_v] = weight[l] % mod;
        return;
    }
    int mid = (l + r) / 2;
    build(cur_v << 1, l, mid);
    build(cur_v << 1 | 1, mid + 1, r);
    arr[cur_v] = (arr[cur_v << 1] + arr[cur_v << 1 | 1]) % mod;
}

int query(int cur_v, int l, int r, int L, int R) {
    int res = 0;
    if (L <= l && r <= R) {
        return arr[cur_v] % mod;
    }
    if (lazy_tag[cur_v]) push_down(cur_v, r - l + 1);
    int mid = (l + r) / 2;
    if (L <= mid) res = (res + query(cur_v << 1, l, mid, L, R)) % mod;
    if (R > mid) res = (res + query(cur_v << 1 | 1, mid + 1, r, L, R)) % mod;
    return res;
}

void update(int cur_v, int l, int r, const int L, const int R, int val) {
    if (L <= l && r <= R) {
        lazy_tag[cur_v] += val;
        arr[cur_v] += val * (r - l + 1);
    } else {
        if (lazy_tag[cur_v])push_down(cur_v, r - l + 1);
        int mid = (l + r) / 2;
        if (L <= mid)update(cur_v << 1, l, mid, L, R, val);
        if (R > mid)update(cur_v << 1 | 1, mid + 1, r, L, R, val);
        arr[cur_v] = (arr[cur_v << 1] + arr[cur_v << 1 | 1]) % mod;
    }
}

////////////
int n, m, r;

int query_range(int x, int y) {
    int ans = 0;

    // 当两个点不在同一条链上
    while (chain_top[x] != chain_top[y]) {
        // 把x点改为所在链顶端的深度更深的那个点
        if (depth[chain_top[x]] < depth[chain_top[y]])
            std::swap(x, y);
        // ans加上x点到x所在链顶端 这一段区间的点权和
        ans = (ans + query(1, 1, n, dfn[chain_top[x]], dfn[x])) % mod;
        // 把x跳到x所在链顶端的那个点的上面一个点
        x = father[chain_top[x]];
    }
    // 直到两个点处于一条链上
    // 把x跳到x所在链顶端的那个点的上面一个点
    if (depth[x] > depth[y]) std::swap(x, y);
    // 把x跳到x所在链顶端的那个点的上面一个点
    return (ans + query(1, 1, n, dfn[x], dfn[y])) % mod;
}

void update_range(int x, int y, int val) {
    val %= mod;
    while (chain_top[x] != chain_top[y]) {
        if (depth[chain_top[x]] < depth[chain_top[y]])std::swap(x, y);
        update(1, 1, n, dfn[chain_top[x]], dfn[x], val);
        x = father[chain_top[x]];
    }
    if (depth[x] > depth[y])std::swap(x, y);
    update(1, 1, n, dfn[x], dfn[y], val);
}

int query_subtree(int x) {
    // 把x跳到x所在链顶端的那个点的上面一个点
    return query(1, 1, n, dfn[x], dfn[x] + size[x] - 1);
}

void update_subtree(int x, int val) {
    update(1, 1, n, dfn[x], dfn[x] + size[x] - 1, val);
}


int main() {
    scanf("%d %d %d %d", &n, &m, &r, &mod);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", w + i);
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs1(r, 0, 1); // r:树的根
    dfs2(r, r);
    build(1, 1, n);
    for (int i = 0; i < m; ++i) {
        int op, x, y, z;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d %d %d", &x, &y, &z);
            update_range(x, y, z);
        } else if (op == 2) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query_range(x, y));
        } else if (op == 3) {
            scanf("%d %d", &x, &z);
            update_subtree(x, z);
        } else {
            scanf("%d", &x);
            printf("%d\n", query_subtree(x));
        }
    }
    return 0;
}