====== 树上启发式合并 ====== ===== 算法简介 ===== 一种离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。 ===== 算法思想 ===== 首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。考虑优化信息合并的过程，类比并查集的启发式合并。显然把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。于是考虑保留重儿子子树的统计信息，然后暴力遍历轻儿子子树，合并结果。具体实现为先 $\text{dfs}$ 处理轻儿子子树的询问，再删除轻儿子子树的统计信息(否则空间复杂度难以承受)。然后处理重儿子子树的询问，但保留重儿子子树的统计信息，最后再次遍历轻儿子子树，然后把信息暴力合并。关于时间复杂度，发现某个节点每被额外统计一次当且仅当他每有一个祖先节点为轻儿子。由于每个节点到根节点最多有 $O(\log n)$ 条轻边，于是每个节点最多被统计 $O(\log n)$ 次，于是总时间复杂度为 $O(n\log n)$。 ===== 算法模板 ===== [[https://www.luogu.com.cn/problem/CF570D|CF570D]] ==== 题意 ==== 给定一个以 $1$ 为根的 $n$ 个节点的树，每个点上有一个小写英文字母。每个点的深度定义为该节点到 $1$ 号节点路径上的点数。每次询问 $a,b$，查询以 $a$ 为根的子树内深度为 $b$ 的节点上的字母重新排列之后是否能构成回文串。 ==== 题解 ==== 考虑字符串排序后能构成回文串的条件，发现只要出现字符串中出现奇数次的字符不超过一种就行。于是只需要维护每个节点子树的每个深度的每种字符个数就行了。 ps. 字母总共就 $26$ 种，考虑状压异或，然后根据 $dfs$ 序建立 $n$ 棵线段树维护深度为 $1\sim n$ 的节点可以实现在线查找。


const int MAXN=5e5+5;
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt].to=v;
	edge[edge_cnt].next=head[u];
	head[u]=edge_cnt;
}
char buf[MAXN];
int cnt[MAXN][30];
bool ans[MAXN];
vector > query[MAXN];
bool check(int d){
	int temp=0;
	_for(i,0,26)temp+=cnt[d][i]&1;
	return temp<=1;
}
int d[MAXN],sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
int h_son[MAXN],mson[MAXN];
void dfs_1(int u,int depth){
	sz[u]=1;d[u]=depth;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		dfs_1(v,depth+1);
		sz[u]+=sz[v];
		if(sz[v]>mson[u]){
			h_son[u]=v;
			mson[u]=sz[v];
		}
	}
}
void update_node(int u,int v){cnt[d[u]][buf[u]-'a']+=v;}
void update_tree(int u,int v){
	_for(i,0,sz[u])
	update_node(node_id[dfs_id[u]+i],v);
}
void dfs_2(int u,bool del){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==h_son[u])continue;
		dfs_2(v,true);
	}
	if(h_son[u])dfs_2(h_son[u],false);
	update_node(u,1);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==h_son[u])continue;
		update_tree(v,1);
	}
	_for(i,0,query[u].size())
	ans[query[u][i].first]=check(query[u][i].second);
	if(del)update_tree(u,-1);
}
int main()
{
	int n=read_int(),q=read_int(),root=1,u,d;
	_rep(i,2,n)
	Insert(read_int(),i);
	scanf("%s",buf+1);
	_for(i,0,q){
		u=read_int(),d=read_int();
		query[u].push_back(make_pair(i,d));
	}
	dfs_1(root,root);
	dfs_2(root,false);
	_for(i,0,q){
		if(ans[i])
		puts("Yes");
		else
		puts("No");
	}
	return 0;
}

===== 算法练习 ===== ==== 习题一 ==== [[https://www.luogu.com.cn/problem/CF600E|CF600E]] === 题意 === 给定一个以 $1$ 为根的 $n$ 个节点的树，每个结点都有一种颜色。求每个节点所在子树种数量最多的颜色(如果有多个满足条件的颜色则将所有颜色编号相加)。 === 题解 === 题目难度不高，这里仅给出代码供参考。


const int MAXN=1e5+5;
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt].to=v;
	edge[edge_cnt].next=head[u];
	head[u]=edge_cnt;
}
int color[MAXN],cnt[MAXN],max_c;LL sum_c,ans[MAXN];
int sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
int h_son[MAXN],mson[MAXN];
void dfs_1(int u,int fa){
	sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs_1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>mson[u]){
			h_son[u]=v;
			mson[u]=sz[v];
		}
	}
}
void add_node(int u){
	cnt[color[u]]++;
	if(cnt[color[u]]>max_c)
	max_c=cnt[color[u]],sum_c=color[u];
	else if(cnt[color[u]]==max_c)
	sum_c+=color[u];
}
void add_tree(int u){
	_for(i,0,sz[u])
	add_node(node_id[dfs_id[u]+i]);
}
void del_tree(int u){
	_for(i,0,sz[u])
	cnt[color[node_id[dfs_id[u]+i]]]--;
}
void dfs_2(int u,int fa,bool del){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==h_son[u]||v==fa)continue;
		dfs_2(v,u,true);
	}
	if(h_son[u])dfs_2(h_son[u],u,false);
	add_node(u);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==h_son[u]||v==fa)continue;
		add_tree(v);
	}
	ans[u]=sum_c;
	if(del)max_c=sum_c=0,del_tree(u);
}
int main()
{
	int n=read_int(),root=1,u,v;
	_rep(i,1,n)
	color[i]=read_int();
	_for(i,1,n){
		u=read_int();
		v=read_int();
		Insert(u,v);Insert(v,u);
	}
	dfs_1(root,0);
	dfs_2(root,0,false);
	_rep(i,1,n)
	space(ans[i]);
	return 0;
}

==== 习题二 ==== [[https://www.luogu.com.cn/problem/CF1009F|CF1009F]] === 题意 === 给定一个以 $1$ 为根的 $n$ 个节点的树，定义 $d(u,x)$ 为 $u$ 的子树中到 $u$ 距离为 $x$ 的节点数。对于每个点，求一个最小的 $k$，使得 $d(u,k)$ 最大。 === 题解 === 题目难度不高，这里仅给出代码供参考。


const int MAXN=1e6+5;
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt].to=v;
	edge[edge_cnt].next=head[u];
	head[u]=edge_cnt;
}
int color[MAXN],cnt[MAXN],max_c,ans_d,ans[MAXN];
int d[MAXN],sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
int h_son[MAXN],mson[MAXN];
void dfs_1(int u,int fa,int depth){
	d[u]=depth;sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs_1(v,u,depth+1);
		sz[u]+=sz[v];
		if(sz[v]>mson[u]){
			h_son[u]=v;
			mson[u]=sz[v];
		}
	}
}
void add_node(int u){
	cnt[d[u]]++;
	if(cnt[d[u]]>max_c||(cnt[d[u]]==max_c&&d[u]



==== 习题三 ====

[[https://www.luogu.com.cn/problem/CF741D|CF741D]]

=== 题意 ===

给定一个以 $1$ 为根的 $n$ 个节点的树，树上每条边代表一个英文小写字母($a\sim v$)。对于每个点，求其子树中的最长回文路径。

=== 题解 ===

显然树上启发式合并不能直接统计路径，想办法把路径转化为点权。

考虑状压异或，令每个节点点权为根节点到该节点的路径的字母的异或和。

则任意两点间路径构成回文串等价于这两点点权异或为 $0$ 或者恰为 $2$ 的幂次。

对每个结点的答案，先考虑经过根节点的路径贡献，可以使用桶记录每个点权出现的最大深度，利用深度可以得到路径长度。

对与子树中的路径，可以从子树向上合并答案。

时间复杂度 $O(cn\log n)$，空间复杂度 $O(2^c)$，其中 $c$ 为字母种类数。



const int MAXN=5e5+5,MAXS=22;
struct Edge{
	int to,w,next;
}edge[MAXN];
int head[MAXN],edge_cnt;
void Insert(int u,int v,int w){
	edge[++edge_cnt]=Edge{v,w,head[u]};
	head[u]=edge_cnt;
}
int c[1<mson[u]){
			h_son[u]=v;
			mson[u]=sz[v];
		}
	}
}
int query_node(int u){
	int ans=c[w[u]]+d[u];
	_for(i,0,MAXS){
		if(c[w[u]^(1<ans)
		ans=c[w[u]^(1<