# POW#1 - Small To Large - Editorial

Bài này chúng ta có thể giải bằng kĩ thuật [Small To Large](https://vnoi.info/wiki/algo/data-structures/disjoint-set-union.md#k%C4%A9-thu%E1%BA%ADt-g%E1%BB%99p-set-small-to-large-merging).

Ta có thể mô hình hóa công ty này ở dạng cây với đỉnh gốc là $1$. Bài toán bây giờ chuyển đổi thành, với mỗi truy vấn, xác định xem có bao nhiêu màu có số lần xuất hiện trong đoạn $[1,k]$ trong cây con gốc $u$.

Ta gọi $S(u)$ là tập các cặp giá trị $(x,y)$, mang ý nghĩa màu $x$ xuất hiện $y$ lần $(y > 0)$ trong cây con gốc $u$ hiện tại ta đang xét. Ở đây, ta định nghĩa $S(u)(x) = y$. Đồng thời gọi $res(u)$ là đáp án nếu truy vấn đỉnh $u$.

Đối với quá trình gộp tập màu của cây con hiện tại của đỉnh $u$ với tập màu của cây con của đỉnh $v$ ($v$ là con trực tiếp của $u$), hay thực chất là hợp tập $S(v)$ vào với $S(u)$, ta làm như sau:
- Kí hiệu $|S(u)|$ là độ lớn của tập $S(u)$. Nếu $|S(v)| > |S(u)|$, ta đảo giá trị hai tập này cho nhau và gán $res(u) = res(v)$, tức là giờ thay vì hợp tập $v$ vào tập $u$, ta đi hợp tập $u$ vào tập $v$. Điều này vẫn cho ra kết quả tập mới không đổi, nhưng do ta chỉ duyệt tập có độ lớn bé hơn, nên ta sẽ thu được độ phức tạp tốt hơn. Chứng minh chi tiết các bạn có thể đọc ở phần link hướng dẫn bên trên.
- Giờ ta duyệt qua từng phần tử $(x,y)$ trong $S(v)$:
- Gọi $val = S(u)(x)$, giờ ta có hai trường hợp:
- Nếu $val = 0$ và $y <= k$, tức là màu $x$ chưa xuất hiện ở trong tập $S(u)$, và do khi gộp hai tập lại, màu này sẽ xuất hiện không quá $k$ lần nên ta cần ***tăng*** $res(u)$ lên $1$ đơn vị.
- Nếu $0 < val \le k$ và $val + y > k$, tức là trước đó màu $x$ đã xuất hiện rồi và số lần xuất hiện của nó thì nằm trong khoảng $[1,k]$, vậy nên khi gộp hai tập vào và ta làm số lần xuất hiện của nó vượt quá $k$, ta cần ***giảm*** $res(u)$ đi một đơn vị.
- Sau đó, nếu chưa tồn tại màu $x$ trong tập $S(u)$ (trường hợp $val=0$) thì ta thêm phần tử $(x,y)$ vào $S(u)$, ngược lại ta xóa phần tử $(x,val)$ ra và thay bằng phần tử $(x,y+val)$.
- Dễ thấy, ta có thể biểu diễn tập $S$ và các phép đảo giá trị tập, thêm, xóa phần tử bằng cấu trúc dữ liệu ```std::map```. Lưu ý rằng việc đảo giá trị tập bằng ```std::map``` chỉ mất $O(1)$.

Độ phức tạp: $O(N \times {\log_{N}}^2)$

**Code tham khảo**:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m,k,q;
vector<int> adj[N];
map<int,int> mp[N];
int res[N];
int c[N];
void dfs (int u, int p) {
	mp[u][c[u]]++;
	res[u] = 1; 
	for (auto v : adj[u]) {
		if (v == p) continue;
		dfs(v,u);
		if (mp[u].size() < mp[v].size()) {
			swap(mp[u],mp[v]);
			res[u] = res[v];
		}
		for (auto it : mp[v]) {
			int x = mp[u][it.first];
			if (x == 0) {
				if (x + it.second <= k) res[u]++;
			}
			else {
				if (x <= k && x + it.second > k) res[u]--;
			}
			mp[u][it.first] += it.second;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i=2; i<=n; i++) {
		int u; cin >> u;
		adj[u].push_back(i);
	}
	for (int i=1; i<=n; i++) cin >> c[i];
	dfs(1,0);
	cin >> q;
	while (q--) {
		int u; cin >> u; 
		cout << res[u] << '\n';
	}
}