线段树合并的作用在于把子节点的信息直接合并在父节点身上来同时会覆盖子节点的信息来保证内存的正确性

可以直接新开节点这样就不会修改儿子信息了

维护父节点和子节点的关系，如树上逆序对

树上逆序对
直接把子树信息合并过来,然后对当前树进行查询,当然可以主席树在线维护

int t,n,m,idx;
struct code{
    int l,r;
    int cnt;
}tr[N*40];

vector<int> v;
int a[N],ans[N],root[N];
vector<int> g[N];
void pushup(int p){
    tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
}
void change(int& p,int l,int r,int v,int val){
    if(!p) p = ++idx;
    if(l==r){
        tr[p].cnt += val;
        return ;
    }
    int mid = l+r>>1;
    if(v<=mid) change(tr[p].l,l,mid,v,val);
    else change(tr[p].r,mid+1,r,v,val);
    pushup(p);
}
int query(int& p,int l,int r,int L,int R){
    if(!p) return 0;
    if(L <= l and r <= R) return tr[p].cnt;
    int mid = l+r>>1;
    int res = 0;
    if(L<=mid) res+=query(tr[p].l,l,mid,L,R);
    if(R>mid)  res+=query(tr[p].r,mid+1,r,L,R);
    return res;
}
int merge(int p,int q,int l,int r){
    if(!p or !q) return p+q;
    if(l==r){
        tr[p].cnt += tr[q].cnt;
        return p;
    }
    int mid = l+r>>1;
    tr[p].l=merge(tr[p].l,tr[q].l,l,mid);
    tr[p].r=merge(tr[p].r,tr[q].r,mid+1,r);
    pushup(p);
    return p;
}
void dfs(int u,int fa){

    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        root[u]=merge(root[u],root[v],1,m);
    }
    ans[u]=query(root[u],1,m,a[u]+1,m);
    change(root[u],1,m,a[u],1);
}
void solve(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m=v.size();

    auto find = [&](int x){
        return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    };

    for(int i=1;i<=n;i++) a[i]=find(a[i]);

    for(int i=2;i<=n;i++){
        int x; cin>>x;
        g[x].push_back(i);
        g[i].push_back(x);
    }

    dfs(1,-1);

    for(int i=1;i<=n;i++) cout << ans[i] << endl;

    return ;
}

种类差分,然后用线段树合并结合起来,如果是普通的差分的话是只有一维可以直接合并
但是由于有多个种类所以需要开权值线段树来维护

雨天的尾巴

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=100010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int p[N][21],ans[N];
int d[N];
vector<int> g[N];

void dfs1(int u,int fa){ // 得到d 和 p数组
    d[u] = d[fa] + 1;
    p[u][0] = fa;
    for(int i=1;i<=20;i++) p[u][i] = p[p[u][i-1]][i-1]; 
    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
    }
}
int lca(int a,int b){
    if(d[a]<d[b]) swap(a,b);

    while(d[a]>d[b])
        a = p[a][(int)log2(d[a]-d[b])];
    if(a==b) return a;

    for(int j=(int)log2(d[a]);j>=0;j--)
        if(p[a][j]!=p[b][j])
            a=p[a][j],b=p[b][j];

    return p[a][0];
}

struct code{
    int l,r;
    int pos;
    int cnt;
}tr[81*N];
int rt[N];
int idx;

void pushup(int p){ // 哪一个救济粮最多
    if(tr[tr[p].l].cnt>=tr[tr[p].r].cnt) tr[p].cnt = tr[tr[p].l].cnt,tr[p].pos = tr[tr[p].l].pos;
    else tr[p].cnt = tr[tr[p].r].cnt,tr[p].pos = tr[tr[p].r].pos;
}

void change(int&p,int l,int r,int pos,int val){ 
    if(!p) p = ++idx;
    if(l==r){
        tr[p].cnt += val;
        tr[p].pos = l; // 他的位置就是l // 表示l这个种类的救济粮食+=val
        return ;
    }
    int mid = l+r>>1;
    if(pos<=mid) change(tr[p].l,l,mid,pos,val);
    else change(tr[p].r,mid+1,r,pos,val);
    pushup(p);
}
int merge(int p,int q,int l,int r){ //由于使用了差分所以说需要合并上来才是当前节点的真实情况
    if(!p or !q) return p+q;
    if(l==r){
        tr[p].cnt += tr[q].cnt; // 表示种类 数量
        tr[p].pos = l; // 表示这是数
        return p;
    }
    int mid = l+r>>1;
    tr[p].l=merge(tr[p].l,tr[q].l,l,mid);
    tr[p].r=merge(tr[p].r,tr[q].r,mid+1,r);
    pushup(p);
    return p;
}
void dfs2(int u,int fa){
    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs2(v,u);
        rt[u] = merge(rt[u],rt[v],1,N);
    }
    if(tr[rt[u]].cnt) ans[u] = tr[rt[u]].pos;
}
void solve(){

    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1,0); // 目的是为了 可以求解lca 

    while(m--){
        int a,b,c; cin>>a>>b>>c;
        int t = lca(a,b);
        change(rt[a],1,N,c,1),change(rt[b],1,N,c,1);
        change(rt[t],1,N,c,-1); // 在权值线段树上加上某一段

        if(p[t][0]) change(rt[p[t][0]],1,N,c,-1);
    }
    dfs2(1,0);

    for(int i=1;i<=n;i++) cout << ans[i] << endl;
    cout << endl;

    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
         solve();
    }
}