题目链接：传送门

Description

给你一颗nn个点的树 每个点有一种颜色 问你对于每一条边，去掉这条边之后剩下的两个部分的颜色集合交集的大小

Constraints

n≤105n\le 10^5

Input

The input contains at most 15 sets. For each set:

The first line contains an integer nn (2≤n≤1052\le n\le10^5).

The second line contains nn integers c1,c2,...,cnc_1,c_2,...,c_n (1≤ci≤n1\le c_i\le n).

The i-th of the last (n−1)(n-1) lines contains2 2 integers ai,bi (1≤ai,bi≤n1\le a_i,b_i\le n).

Output

For each set,(n−1) (n-1) integers R1,R2,...,Rn−1R_1,R_2,...,R_{n-1}

Sample Input

4

1 2 2 1

1 2

2 3

3 4

5

1 1 2 1 2

1 3

2 3

3 5

4 5

Sample Output

1

2

1

1

1

2

1

Solution

首先题意可以转化为 求出每个子树内每种颜色出现次数，如果次数等于00或者等于这种颜色在整棵树里出现的次数的话显然这个颜色就没有贡献，否则就有贡献

所以我们就可以直接树上启发式合并，用map或者线段树合并都行

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 2e5 + 100;

int N, M, e, Begin[Maxn], Next[Maxn << 1], To[Maxn << 1], C[Maxn << 1], Id[Maxn << 1];
int Sum[Maxn], Ans[Maxn];
map <int, int> Cnt[Maxn];

inline void add_edge (int x, int y, int z)
{
	To[++e] = y;
	Next[e] = Begin[x];
	Begin[x] = e;
	Id[e] = z;
}

void dfs (int x, int f, int id)
{
	Cnt[x][C[x]] = 1;
	if (Sum[C[x]] > 1) Ans[id] ++;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == f) continue;
		dfs(y, x, Id[i]);
		if (Cnt[x].size() < Cnt[y].size()) { swap(Cnt[x], Cnt[y]); Ans[id] = Ans[Id[i]]; }
		for (auto now : Cnt[y])
		{
			if (Cnt[x].count(now.x))
			{
				Cnt[x][now.x] += now.y;
				if (Cnt[x][now.x] == Sum[now.x]) Ans[id] --;
			}
			else
			{
				Cnt[x][now.x] = now.y;
				if (Cnt[x][now.x] < Sum[now.x]) Ans[id] ++;
			}
		}
	}
}

inline void Init()
{
	memset(Begin, 0, sizeof Begin);
	memset(Sum, 0, sizeof Sum);
	memset(Ans, 0, sizeof Ans);
	e = 0;
}

int main()
{
#ifdef hk_cnyali
	freopen("I.in", "r", stdin);
	freopen("I.out", "w", stdout);
#endif
	while (~scanf("%d", &N))
	{
		Init();
		for (int i = 1; i <= N; ++i) Cnt[i].clear(), C[i] = read(), Sum[C[i]] ++;
		for (int i = 1; i < N; ++i)
		{
			int x = read(), y = read();
			add_edge (x, y, i);
			add_edge (y, x, i);
		}
		dfs(1, 0, 0);
		for (int i = 1; i < N; ++i) printf("%d\n", Ans[i]);
	}
	return 0;
}