启发式算法是基于人类的经验和直观感觉，对一些算法的优化。
例题：给出一棵 n 个节点以 1 为根的树，节点 u 的颜色为 $c_u$，现在对于每个结点 u 询问以 u 为根的子树里一共出现了多少种不同的颜色。

暴力是对n个节点统计n种颜色，n方级别复杂度。还容易爆空间。
1.离线询问
2.重链剖分
3.如果O(1)继承重儿子，暴力统计轻儿子。根节点到树上任意节点的轻边数不超过$ \log n $条，一个节点的被遍历的次数等于它到根节点路径上的轻边数 +1（之所以要 +1 是因为它本身要被遍历到）。所以复杂度nlogn。

具体做法是离线询问，只用一个cnt数组，第二次dfs时先dfs轻儿子，但是不修改cnt数组，然后O(1)继承重儿子，即dfs重儿子并修改cnt数组。然后再遍历轻儿子加上贡献。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int N  = 2e5+10;
int n;
vector<vector<int>> g;

int sz[N],son[N],dfn[N],rnk[N];
int ans[N],cnt[N],totcolor,col[N];

void add(int u){
    if(cnt[col[u]]==0) ++totcolor;
    cnt[col[u]] ++ ; 
}
void del(int u){
    cnt[col[u]] -- ; 
    if(cnt[col[u]]==0) --totcolor;
}
int getAns(){
    return totcolor;
}
void dfs1(int u,int fa){
    dfn[u] = ++*dfn;
    rnk[dfn[u]] = u;
    sz[u] = 1;
    son[u] = -1;
    for(auto v:g[u]){
        if(v!=fa){
            dfs1(v,u);
            sz[u ] += sz[v];
            if(son[u]==-1||sz[son[u]]<sz[v]) son[u] = v;
        }
    }
}
void dfs2(int u,int fa,bool keep){
    for(auto v:g[u]){
        if(v!=fa && v!=son[u]){
            dfs2(v,u,0);
        }
    }
    if(son[u]!=-1) dfs2(son[u],u,true);
    for(auto v:g[u]){
        if(v!=fa && v!=son[u]){
            for(int i=dfn[v];i<dfn[v]+sz[v];i++){
                add(rnk[i]);
            }
        }
    }
    add(u);
    ans[u] = getAns();
    if(!keep){
        for(int i=dfn[u];i<dfn[u]+sz[u];i++) del(rnk[i]);
    }
}


void solve(){
    cin>>n;
    g = vector<vector<int>>(n+1);

    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) cin>>col[i];
    dfs1(1,0);
    dfs2(1,0,false);
    int m; cin>>m;
    while(m--){
        int x; cin>>x;
        cout<<ans[x]<<endl;
    }
}

int main(){     
    ifstream test_file("in.txt");
    if (test_file) {
        freopen("in.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}

map模版（$nlog^2n$）

复杂度多了个log，但是好写很多，而且可以回溯时可以更好的维护信息。
如https://codeforces.com/gym/105176这个N题，当子树颜色数量大于等于k个时，要将子树删除，如果和nlogn模版一样，子树的siz是变化的，因此dfs2时统计子树信息时会出现问题（但是肯定也可以做，就是要改改）。如果用map模板的话直接无脑合并就完了。

vector<map<int,int>*> cnt;
void dfs1(int u,int fa){
    son[u] = -1;siz[u] = 1;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        if(!vis[v]){
            siz[u] += siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]]) son[u] = v;          
        }
    }
    if(son[u]!=-1) cnt[u] =  cnt[son[u]];
    else cnt[u] = new map<int,int>();
    (*cnt[u])[col[u]]++;
    for(auto v:g[u]){
        if(v!=fa&& v!=son[u] && !vis[v]){
            for(auto x:*cnt[v]){
                (*cnt[u])[x.first] += x.second; 
            }
        }
    }
    if((*cnt[u]).size() >= k){
        siz[u] = 0,cnt[u]->clear();vis[u] = true;
        tot++;
    }
}