Codeforces Round #695 (Div. 2) E. Distinctive Roots in a Tree

admin管理员组

文章数量:1622541

题目链接
You are given a tree with n n n vertices. Each vertex i i i has a value a i a_i ai​ associated with it.

Let us root the tree at some vertex v v v. The vertex v v v is called a distinctive root if the following holds: in all paths that start at v v v and end at some other node, all the values encountered are distinct. Two different paths may have values in common but a single path must have all distinct values.

Find the number of distinctive roots in the tree.

Input

The first line of the input contains a single integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2\cdot10^5 1≤n≤2⋅105) — the number of vertices in the tree.

The next line contains n n n space-separated integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​ ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai​≤109).

The following n − 1 n-1 n−1 lines each contain two space-separated integers u u u and v v v ( 1 ≤ u 1 \le u 1≤u, v ≤ n v \le n v≤n), denoting an edge from u u u to v v v.

It is guaranteed that the edges form a tree.

Output

Print a single integer — the number of distinctive roots in the tree.

Examples

input

5
2 5 1 1 4
1 2
1 3
2 4
2 5

output

3

input

5
2 1 1 1 4
1 2
1 3
2 4
2 5

output

0

Note

In the first example, 1 1 1, 2 2 2 and 5 5 5 are distinctive roots.

显然当某个点到所有根节点的每一条路径上的元素都不重复则该点为满足条件的点。
假设选定节点 1 1 1 为根节点，则对于某个节点 x x x ，它的某子节点 y y y 为根的子树中存在元素 a [ x ] a[x] a[x] ，则路径 1 ∼ x 1\sim x 1∼x 上的节点都不满足条件；同样的，如果除了 x x x 为根子树外的某个节点的值为 a [ x ] a[x] a[x] ，则以 x x x 为根的子树上的点都不满足条件。
上述两种情况均可以通过差分把不满足条件的节点设为某个非 0 0 0 整数，最后统计值为 0 0 0 的节点个数即为答案。

#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + (c & 15);
        c = getchar();
    }
    return f * fu;
}

const int N = 2e5 + 10;
int head[N], ver[N << 1], Next[N << 1], tot;
int a[N], n;
vector<int> seq;
int num[N], cnt[N], f[N], ans;

inline void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

void dfs(int x, int fa) {
    int tmp1 = cnt[a[x]];
    cnt[a[x]]++;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (y == fa)continue;
        int tmp2 = cnt[a[x]];
        dfs(y, x);
        if (cnt[a[x]] != tmp2)f[1]++, f[y]--;
    }
    if (cnt[a[x]] - tmp1 != num[a[x]])f[x]++;
}

void dfs(int x, int fa, int now) {
    if (!now)ans++;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (y == fa)continue;
        dfs(y, x, now + f[y]);
    }
}

int main() {
    n = qr();
    for (int i = 1; i <= n; ++i)seq.push_back(a[i] = qr());
    sort(seq.begin(), seq.end());
    seq.erase(unique(seq.begin(), seq.end()), seq.end());
    for (int i = 1; i <= n; i++)
        num[a[i] = lower_bound(seq.begin(), seq.end(), a[i]) - seq.begin() + 1]++;
    for (int i = 1; i <= n - 1; ++i) {
        int x = qr(), y = qr();
        add(x, y), add(y, x);
    }
    dfs(1, 0), dfs(1, 0, f[1]);
    printf("%d\n", ans);
    return 0;
}

本文标签： DivcodeforcestreeRootsdistinctive