Segment tree merge board

Segment tree merging is often used in tree problems , Suppose each point has a weight segment tree to store information , So if we want to know the total information of a subtree , You need to merge the segment tree of all points in the subtree to the segment tree of the root node of the subtree .

How to synthesize ？ Suppose it is for two full segment trees , Start directly at the bottom （ Suppose the underlying information is recorded in a1[N] and a2[N] in ） Give Way a1[i] += a2[i], Then regenerate a tree . This is the most violent way , Complexity is not ok Of .

But in fact, segment trees are often dissatisfied , So we just need to dynamically open the segment tree , Can achieve a better merger . The final complexity is O(nlogn), Prove slightly .

Example ：[Vani There's a date ] The tail of a rainy day /【 Templates 】 Line tree merge - Luogu

This problem requires tree difference and line segment tree merging .

1. The difference on the tree is reflected in ：x~y part ,z Type and quantity of grain +1, Equivalent to 1~x Of z species +1, 1~y Of z species +1, 1~lca Of z species -1, 1~fa[lca] Of z species -1. These four parts together form a tree difference .

int u,v,w; cin>>u>>v>>w;
int l = LCA(u,v); //l yes u and v The common ancestor of 
upd(rt[u], 1, 1e5, w, 1); // Maintain four differential , Thus forming u~v part w Number +1 The effect of 
upd(rt[v], 1, 1e5, w, 1);
upd(rt[l], 1, 1e5, w, -1);
upd(rt[f[l][0]], 1, 1e5, w, -1);

 2. The merging of segment trees is reflected in ： When you want to convert the difference into value , To calculate the merged segment tree of the subtree .

for instance ,1 Have two children ,2 and 3, Well, you know 1 Information about , Will the 2 and 3 The line segment tree of is synthesized into 1 On .

code：

Add a little attention ： The space of segment tree must be open enough , want 4*n*logn Space （ There are 4 individual upd）

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
const int N = 1e5+5;
int n,m,ans[N],f[N][30],lg[N],d[N];
int rt[N], ls[N*80], rs[N*80], cnt=0; // Root node , Left and right children , Current number 
pair<int,int> t[N*80]; // The tree itself ,{ Amount of relief grain , Type number }
vector<int> g[N];

void dfs(int u,int fa){
    f[u][0] = fa, d[u] = d[fa]+1;
    FOR(i,1,lg[d[u]])
        f[u][i] = f[f[u][i-1]][i-1];
    for(int v:g[u])
        if(v!=fa) dfs(v,u);
}
int LCA(int x,int y){
    if(d[x] < d[y]) swap(x,y);
    while(d[x] > d[y]) x = f[x][lg[d[x]-d[y]]];
    if(x==y) return x;
    for(int k=lg[d[x]]; k>=0; k--)
        if(f[x][k] != f[y][k]) {x=f[x][k]; y=f[y][k];}
    return f[x][0];
}
void pushup(int o){
    // Operations on the same segment tree , A node collects information about its two sons , Get this interval { The largest number , Corresponding to the type of grain }
    t[o] = max(t[ls[o]], t[rs[o]]);
}
void upd(int&o,int l,int r,int pos,int val){
    // Give it to o It's a tree pos Location +val
    if(!o) o = ++cnt; // If there are no nodes , Create a new one 
    if(l==r){
        t[o].first += val; //pos The amount of grain of each kind +val
        t[o].second = -pos; // The grain type marked here is pos（ The negative sign here is for convenience ）
        return;
    }
    int mid = l+r>>1;
    if(pos<=mid) upd(ls[o],l,mid,pos,val);
    else upd(rs[o],mid+1,r,pos,val);
    pushup(o);
}
int merge(int o,int p,int l,int r){
    // hold p Trees synthesize to o on the tree , Return the root node number of the new tree 
    if(o==0 || p==0) return o+p; // There is a tree empty , Directly replace with another tree 
    if(l==r) {t[o].first += t[p].first; return o;} // Are not empty , And to the leaf node , hold p Synthesize to o On 
    int mid = l+r>>1;
    ls[o] = merge(ls[o],ls[p],l,mid); // The left half and the right half are combined recursively 
    rs[o] = merge(rs[o],rs[p],mid+1,r);
    pushup(o); // After the son node successfully synthesizes the information of another tree , Re maintain father's information 
    return o; // Don't forget to return to the original node 
}
void calc(int u,int fa){
    for(int v:g[u]){
        if(v==fa) continue;
        calc(v,u);
        rt[u] = merge(rt[u],rt[v],1,1e5); // The core step of segment tree merging ！ hold rt[v] This tree composes to rt[u] Up , The synthetic range is [1,1e5]
    }
    if(t[rt[u]].first!=0) ans[u] = -t[rt[u]].second;
}
inline void solve(){
    cin>>n>>m;
    FOR(i,1,n-1){
        int u,v; cin>>u>>v;
        g[u].push_back(v), g[v].push_back(u);
    }

    FOR(i,2,n) lg[i]=lg[i>>1]+1; // Preprocessing log2(i)
    dfs(1,0); // Preprocessing out multiplication jump LCA Information about 

    FOR(i,1,m){
        int u,v,w; cin>>u>>v>>w;
        int l = LCA(u,v); //l yes u and v The common ancestor of 
        upd(rt[u], 1, 1e5, w, 1); // Maintain four differential , Thus forming u~v part w Number +1 The effect of 
        upd(rt[v], 1, 1e5, w, 1);
        upd(rt[l], 1, 1e5, w, -1);
        upd(rt[f[l][0]], 1, 1e5, w, -1);
    }
    calc(1,0); // Tree like dp, Merge segment trees （ Difference -> value ）
    FOR(i,1,n) cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}