**Refereances:**
- Euler tour: https://vnoi.info/wiki/algo/graph-theory/euler-tour-on-tree.md
- Small to large: https://usaco.guide/plat/merging?lang=cpp
# Content
[toc]

# Bài toán
- Đề bài: Cho $1$ cây có $n$ node và $n-1$ cạnh. Mỗi node $i$ có 1 giá trị $c_i$. Với mỗi cây con đỉnh $i$, số giá trị riêng biệt của các node trong nó.
- Input:
Dòng đầu tiên là 1 số nguyên $n$ $(1 \le N \le 1e5)$.
Dòng thứ hai $n$ số nguyên $c_i$ $(1 \le c_i \le n)$.
$n-1$ dòng tiếp theo là mỗi dòng gồm hai số nguyên $u$, $v$ $(1 \le u, v \le n)$, có một cạnh nối từ đỉnh $u$ tới đỉnh $v$.
- Sample test:

:::info
**Input:**
5
2 3 2 2 1
1 2
1 3
3 4
3 5

**Output:**
3 1 2 1 1
:::
- Link bài: https://cses.fi/problemset/task/1139
# Thuật toán Ngây thơ
- Lưu mỗi đỉnh $i$, một $map$ để đếm số lần xuất hiện của từng giá trị trong cây con của $i$, đáp án là size của $map$.
- Ta dùng một hàm $DFS$ để chạy đệ quy tính các đỉnh con trước sau đó tính đỉnh cha bằng cách gộp các map ở các đỉnh con trực tiếp của nó.
- Thao tác gộp hai $map$ tốn thời gian $O(N*logN)*O(logN)$ ($map$ tốn $O(logN)$ mỗi operation) và ta phải thực hiện theo tác $N$ lần nên tổng độ phức tạp là $O(N^2*log^2N)$. Điều này là quá lâu để thuật toán có thể chạy được.
# Tối ưu thời gian (Small to large)
- Gọi số của hai $map$ cần gộp là $X, Y$ $(|X| \le |Y|)$, do đó số phần từ của $map$ sau khi gộp ít nhất là $2*|X|$.
- Từ đó, ta thấy được nếu di chuyển một phần tử $K$ lần thì $map$ chứa nó phải có ít nhất $2^K$ phần tử, mà một $map$ chỉ có tối đa $N$ phần tử nên ta chỉ có thể di chuyển $O(logN)$ lần một phần tử.
- Và việc ta cần làm là di chuyển các phần tử từ $map$ này qua $map$ khác chứ không phải là gộp hai $map$ thành một $map$ mới nên ta sẽ chỉ mất thời gian của một $map$, và để tối ưu thì chắc chắn nên di chuyển từ $X$ qua $Y$.
- Từ đó ta thấy được độ phức tạp giảm từ $O(N*log^2N)$ xuống $O(log^2N)$ mỗi thao tác cập nhật từ con lên cha nên tổng độ phức tạp sẽ giảm xuống $O(N^2*log^2N)$ xuống $O(N*log^2N)$. Điều này là đủ để thuật toán có thể chạy.
:::success
:bulb: **Note:** Với một số bài toán, ta có thể tránh được việc phải dùng một cấu trúc dữ liệu(như $set$, $map$, $...$) để lưu trữ thông tin từ đó tránh bị mất đi $O(logN)$ cho các operation của cấu trúc dữ liệu từ đó giảm độ phức tạp xuống còn $O(N*logN)$.
:::
# Tối ưu không gian (Sack)
- Có thể thấy rằng việc sử dụng mỗi node một $map$ tốn rất nhiều không gian và khả năng cao gây tràn bộ nhớ, do đó ta phải nghĩ tới việc có thể hay không sử dụng một hoặc một số lượng $map$ cố định.
- Việc này là hoàn toàn có thể bởi ta thực hiện việc di chuyển $map$ chỉ từ $map$ nhỏ qua $map$ lớn và được lưu lại ở đó nên $map$ nhỏ hoàn toàn không cần thiết để lưu lại cho những node cha.
- Thay vào đó ta có thể lưu lại một $Euler$ $tour$ và ta duyệt qua nó để cập nhật các rồi đưa vào $map$ lớn.
- Thao tác này tối ưu được rất nhiều không gian từ đó có thể biến kĩ thuật này thành một cấu trúc dữ liệu ứng dụng được trên nhiều bài toán, nó được gọi là $Sack$.
# Code mẫu
:::spoiler If you know, you know
:::success :::

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define limit (int)1e18
// pairs
#define mp make_pair
#define f first
#define s second
//loops
#define For(i, a, b) for (int i = (a); i < (b); ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define For2(i, a, b) for (int i = (a); (b) ; ++i)
#define Rof2(i, a, b) for (int i = (b)-1; (a) ; --i)
#define trav(a, x) for (auto &a : x)
//declarations
#define pr pair
#define pq priority_queue
template<class x> using pqg = priority_queue<x, vector<x>, greater<x> >;
template<class x> using prr = pair<x,x>;
// function
#define pb push_back
#define all(x) x.begin(),x.end();
const int N=2e5+10;
vector<int> tree[N];
int n, ans[N], sz[N], in[N], out[N], color[N];
vector<int> tour;
map<int, int> cnt;
void pre(int x, int par)
{
    sz[x]=1,tour.pb(color[x]), in[x]=tour.size()-1;
    trav(i, tree[x]) if(i!=par) pre(i, x), sz[x]+=sz[i];
    out[x]=tour.size()-1;
}
void dfs(int x, int par, int keep)
{
    int idx=0;
    trav(i, tree[x]) if(i!=par && sz[i]>sz[idx]) idx=i;
    trav(i, tree[x])
        if(i!=par && i!=idx) dfs(i, x, 0);
    if(idx) dfs(idx, x, 1);
    cnt[color[x]]++;
    trav(i, tree[x])
    {
        if(i!=par && i!=idx)
            For(j, in[i], out[i]+1) cnt[tour[j]]++;
    }
    ans[x]=cnt.size();
    if(!keep) cnt.clear();
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    For(i, 1, n+1) cin>>color[i];
    For(i, 1, n)
    {
        int a, b;
        cin>>a>>b;
        tree[a].pb(b), tree[b].pb(a);
    }
    pre(1,0), dfs(1, 0, 1);
    For(i, 1, n+1) cout<<ans[i]<<" ";
    return 0;
}

:::