Dsu On Tree/树上启发式合并/静态链分治

解决的问题

用于解决一些处理子树信息的询问，无修改，但是却不容易用普通数据结构维护，如数颜色，众数，可以用 $dfs$ 序转化成区间问题并用莫队维护，但是复杂度为根号级别不够优秀。

Dsu On Tree/树上启发式合并/静态链分治

首先这样的问题都可以通过 $dfs$ 整棵子树，然后把每个点的值插入到数据结构中，最后在这个点通过这个数据结构统计一下答案，这样的复杂度显然是 $O(n^2)$ 的，但是观察一下会发现我们有好多次重复的操作，那么我们就可以每次少 $dfs$ 一棵子树，保留这个子树的答案到上面去，但是这样就意味着其他的子树必须 $dfs$ 两次，但是这样的复杂度被证明为 $n\log n$ 。

放一个模板：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return; 

}

int siz[MAXN],fa[MAXN],son[MAXN],dep[MAXN];

void dfs1(int k)

{

	siz[k] = 1;

	dep[k] = dep[fa[k]] + 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

namespace query

{

	int s[];

	int ans = 0;

	void insert(int v)

	{

		return;

	}

	void reset()

	{

		ans = 0;

		return;

	}

}

void add(int k)

{

	query::insert(val[k]);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		add(e[i].to);

	}

	return;

}

int ans[MAXN];

void calc(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k] || e[i].to == son[k])continue;

		calc(e[i].to);

        query::reset();

	}

	if(son[k] != 0)calc(son[k]);

	query::insert(val[k]);

	query::query(val[k]);

	if(son[k] == 0)return;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k] || e[i].to == son[k])continue;

		add(e[i].to);

	}

	ans[k] = query::ans;

	return;

}

int main()

{

	init();

	dfs1(1);

	calc(1);

	output();

	return 0;

}