最大最小路

import sys
inps = sys.stdin.read().split('\n')

from collections import deque
def count(n, inSet, tree):
    total = 0
    visited = [False] * n
    for i in range(n):
        if not visited[i] and inSet[i]:
            que = deque()
            que.append(i)
            _n = 1
            visited[i] = True
            while que:
                u = que.popleft()
                for v in tree[u]:
                    if not visited[v] and inSet[v]:
                        _n += 1
                        que.append(v)
                        visited[v] = True
            total += _n * (_n - 1) // 2
    return total

def main():
    n, a, b = map(int, inps[0].split(' '))
    ws = list(map(int, inps[1].split(' ')))
    tree = [[] for _ in range(n)]
    for uv in inps[2:-1]:
        u, v = map(int, uv.split(' '))
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)
    total = n * (n - 1) // 2
    
    inA = [w > a for w in ws]
    inB = [w < b for w in ws]
    inAB = [a < w < b for w in ws]

    cntA = count(n, inA, tree)
    cntB = count(n, inB, tree)
    cntAB = count(n, inAB, tree)
    oup = total - (cntA + cntB - cntAB)
    print(oup)


if __name__ == '__main__':
    main()

// 总路径数
// 1...2, 1...3, 1...4, 1...5
// 2...3, 2...4, 2...5
// 3...4, 3...5
// 4...5
// 4 + 3 + 2 + 1 + 0 = n * (n - 1) / 2

//   min < a && max > b
// = 至少一个 < a && 至少一个 > b
// 但是不好统计，所有改用补集思路
//   所有路径 - 坏路径
// = 所有路径 - ((全部 > a) + (全部 < b) - (a < 全部 < b))

// 筛选出的节点不一定是一棵完整的树，需要先合并成n棵树再计算各个树上的路径


#include <cstdint>
#include <cstdio>
#include <vector>

using namespace std;

enum SECTION {
    NONE = 0,
    MORE_THAN_A = 1 << 0,
    LESS_THAN_B = 1 << 1
};


class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        return;
    }

    int find(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }

    void combine(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) {
            return;
        }

        if (rootx > rooty) {
            parent[rooty] = rootx;
            size[rootx] += size[rooty];
        } else {
            parent[rootx] = rooty;
            size[rooty] += size[rootx];
        }
    }

    int64_t calculate() {
        int64_t ret = 0;

        for (int i = 0; i < parent.size(); i++) {
            if ((parent[i] == i) && size[i] > 1) {
                ret += (int64_t)size[i] * (size[i] - 1) / 2;
            }
        }
        return ret;
    }
private:
    vector<int> parent;
    vector<int> size;
};

int main() {
    int n = 0, a = 0, b = 0;
    scanf("%d %d %d", &n, &a, &b);

    int value;
    vector<int> flag(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        if (value > a) {
            flag[i] |= MORE_THAN_A;
        }
        if (value < b) {
            flag[i] |= LESS_THAN_B;
        }
    }

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

    UnionFind bad1(n), bad2(n), bad3(n);
    for (int i = 0; i < n; i++) {
        for (auto j : neighbour[i]) {
            if ((flag[i] & MORE_THAN_A) && (flag[j] & MORE_THAN_A)) {
                bad1.combine(i, j);
            }

            if ((flag[i] & LESS_THAN_B) && (flag[j] & LESS_THAN_B)) {
                bad2.combine(i, j);
            }

            if ((flag[i] & MORE_THAN_A) && (flag[j] & MORE_THAN_A)
             && (flag[i] & LESS_THAN_B) && (flag[j] & LESS_THAN_B)) {
                bad3.combine(i, j);
            }
        }
    }

    int64_t badPath1 = bad1.calculate();
    int64_t badPath2 = bad2.calculate();
    int64_t badPath3 = bad3.calculate();
    int64_t totalPath = (uint64_t)n * (n - 1) / 2;

    printf("%ld\n", totalPath - badPath1 - badPath2 + badPath3);

    return 0;
}

line = [int(item) for item in input().split(" ")]
node_num = line[0]
min_num = line[1]
max_num = line[2]
node_val = [int(item) for item in input().split(" ")]
node_tu = [[0] * node_num for i in range(node_num)]
for i in range(0, node_num - 1):
    line = [int(item) for item in input().split(" ")]
    node_tu[line[0]-1][line[1]-1] = 1
    node_tu[line[1]-1][line[0]-1] = 1

# print(node_tu)

resa = []


def get_next_path(node_tu, searched_path):
    node = searched_path[-1]
    res = []
    for i in range(node_num):
        if node_tu[node - 1][i] == 1 and i + 1 not in searched_path:
            res.append(i + 1)
    return res


def search_path(node_tu, searched_path, res):
    next_path = get_next_path(node_tu, searched_path)
    if not next_path:
        val_list = []
        for item in searched_path:
            val_list.append(node_val[item - 1])
        if min(val_list) <= min_num and max(val_list) >= max_num:
            temp = list(reversed(searched_path))
            if searched_path not in res and temp not in res:
                res.append(searched_path)
    else:
        for node in next_path:
            search_path(node_tu, searched_path + [node], res)


for node in range(1,node_num+1):
    search_path(node_tu, [node,], resa)

print(len(resa))