树上启发式合并，DSU On Tree，静态链分治，用于求解支持离线的树上子树查询问题。
暴力做法，每次做完一棵树就要把它清空，避免对它兄弟造成影响，但是做到它的祖先时又会重新对它做一遍，发现最后一棵树是不需要清空的，于是考虑将节点数最多的留到最后。
首先对树进行轻重链剖分，找出重儿子，在计算答案时，先遍历x的轻儿子，但不保留其影响，之后遍历x的重儿子，保留影响，最后再次遍历x的轻儿子，得到x的答案。
除了重儿子，每次遍历完后要恢复之前的状态。
每次询问一个点x和k，问由多少个点和x由共同的k级祖先。
倍增预处理，将询问离线到x的k级祖先，用cnt数组记录当前子树内不同深度的出现次数。
inline int find(int x,int k){
for(int i=18;~i;i--)if(k>=1<<i)k-=1<<i,x=fa[x][i];
/* for(int i=18;~i;i--)if(k>=dep[x]-dep[fa[x][i]])k-=dep[x]-dep[fa[x][i]],x=fa[x][i];效果一样*/
return x;
}
void dsu(int x,bool isson){
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x])continue;
dsu(y,false);/*先遍历轻儿子*/
}
if(son[x])dsu(son[x],true);/*有重儿子则遍历重儿子*/
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x])continue;
for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++)cnt[dep[mp[j]]]++;/*dfs序映射子树内节点，深度更新*/
}
cnt[dep[x]]++;/*更新x自己的深度*/
for(auto a:v[x])ans[a.id]=cnt[dep[x]+a.k]-1;/*询问点的k级祖先为x，即x的k级后代为询问点，查询相同深度的点的个数并减去询问自己*/
if(isson==false)for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[dep[mp[i]]]--;/*复原*/
}
每个点由颜色，求每棵子树占据主导地位的颜色的编号和。
为每个颜色开一个桶，记录当前最大值和sum，每次由更新操作时比较cnt和最大值，相等则累加sum，cnt大于最大值时更新最大值并重置sum，清除轻儿子贡献时清空最大值和sum.
void dsu(int x,bool isson){
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x]||y==fa[x])continue;
dsu(y,false);
}
if(son[x])dsu(son[x],true);
cnt[col[x]]++;
if(cnt[col[x]]>ma)ma=cnt[col[x]],sum=col[x];
else if(cnt[col[x]]==ma)sum+=col[x];
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x]||y==fa[x])continue;
for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++){
cnt[col[mp[j]]]++;
if(cnt[col[mp[j]]]>ma)ma=cnt[col[mp[j]]],sum=col[mp[j]];
else if(cnt[col[mp[j]]]==ma)sum+=col[mp[j]];
}
}
ans[x]=sum;
if(isson==false){
sum=ma=0;
for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[col[mp[i]]]--;
}
}
每个点由点权，定义一棵树合法当且仅当不存在简单路径的异或和为0，每次可以改变一个点权成为任意数，求最少操作数使得树合法。
假设将x的点权修改为$2{30+x}$，那么所有经过x的路径的异或和都不会为0。为每一个点开一个集合存子树内所有点的dis，即1到该点的异或和，枚举x的儿子y，将y的集合合并到x上面，强制x的size大于y的size，枚举y中每一个元素k，若在x中可以找到a[x]k，那么x需要修改，之后将x的集合清空。
void dfs(int x,int fa){
mp[x][dis[x]]=true;
bool flag=false;
for(auto y:v[x]){
if(y==fa)continue;
dis[y]=dis[x]^a[y];
dfs(y,x);
if(mp[x].size()<mp[y].size())swap(mp[x],mp[y]);
for(auto k:mp[y])if(mp[x].find(a[x]^k.first)!=mp[x].end()){
flag=true;
break;
}
for(auto k:mp[y])mp[x][k.first]=true;
}
if(flag==true)mp[x].clear(),ans++;
}
一片森林，每个点有一个字符串作为名字，每次询问点x的k级子孙共有多少个不同的名字。
unordered_map维护同一个深度的字符串集合，撤销轻儿子操作时则清空它。
void dsu(int x,bool isson){
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x])continue;
dsu(y,false);
}
if(son[x])dsu(son[x],true);
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==son[x])continue;
for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++)cnt[dep[mp[j]]][s[mp[j]]]=true;
}
cnt[dep[x]][s[x]]=true;
for(auto a:v[x])ans[a.id]=cnt[a.x].size();
if(isson==true)return;
for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[dep[mp[i]]].clear();
}
for(int i=1;i<=m;i++){
int x,k;
cin>>x>>k;
v[x].push_back({i,dep[x]+k});
}