线段树合并的时间复杂度是 \(O(m\log n)\) 的（\(m\) 为插入次数）。
int mer(int x,int y){
if(!x||!y)return x^y; t[x]+=t[y];
return L[x]=mer(L[x],L[y]),R[x]=mer(R[x],R[y]),x;
}
因为每个点只会在自己被删除（情况 1）或父亲被删除且自己未删除的（即合并时另一个子树为空，情况 2）情况下被枚举。（被删除指的是在以后的线段树合并中不会被枚举到）。
情况 1 显然是 \(O(m\log n)\) 的，情况 2 只会在父亲被删除时才会被枚举，所以也是 \(O(m\log n)\) 的。所以整体复杂度为 \(O(m\log m)\)。
所以在树上用线段树合并是有时间复杂度保障的，大胆使用即可（常树较大）。
当题目的内存为 \(\texttt{128MB}\) 或 \(\texttt{256MB}\) 时建议加上垃圾回收，避免因为卡内存造成的 \(\texttt{MLE}\) 惨案。
P3605 [USACO17JAN] Promotion Counting P：
随便找的一个简单题，直接线段树合并、区间询问即可。
// qwq
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+12;
int L[N*100],R[N*100],cnt,t[N*100];
int a[N],rt[N],ans[N],n;
vector<int>e[N];
void ins(int& k,int l,int r,int x){
if(!k)k=++cnt;t[k]++;
if(l==r)return;int mid=l+r>>1;
if(x<=mid)ins(L[k],l,mid,x);
else ins(R[k],mid+1,r,x);
}
int ask(int k,int l,int r,int x,int y){
if(x>y||l>r||l>y||x>r)return 0;
if(l>=x&&r<=y)return t[k];int mid=l+r>>1;
return ask(L[k],l,mid,x,y)+ask(R[k],mid+1,r,x,y);
}
int mer(int x,int y){
if(!x||!y)return x^y; t[x]+=t[y];
return L[x]=mer(L[x],L[y]),R[x]=mer(R[x],R[y]),x;
}
void dfs(int u){
ins(rt[u],1,1e9,a[u]);
for(int v:e[u])dfs(v),rt[u]=mer(rt[u],rt[v]);
ans[u]=ask(rt[u],1,1e9,a[u]+1,1e9);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2,x;i<=n;i++)cin>>x,e[x].push_back(i);
dfs(1);
for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
return 0;
}