线段树合并模板

我认为可能出现问题的地方就是每一个点初始化时maxn的初始值，update和merge，当然可能别的地方也有。

目前已知建图，lca相关的都没有问题

样例过了，拍出一个hack：

6 4
6 5
2 3
4 2
3 5
1 4
3 3 4
2 3 5
6 6 1
2 6 2

#include <iostream>
#include <string.h>
using namespace std;
inline int read();
int n,m;
struct Edge{
    int v,nxt;
}e[200005];
int p[100005],eid;
inline void init(){
    memset(p,-1,sizeof(p));
    eid = 0;
}
inline void insert(int u,int v){
    e[eid].v = v;
    e[eid].nxt = p[u];
    p[u] = eid++;
}

int fa[100005][25];

int dep[100005];

void dfs(int u,int last){
    for(int i = p[u];i != -1;i = e[i].nxt){
        int v = e[i].v;
        if(v == last) continue;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;
        dfs(v,u);
    }
    return;
}

inline int lca(int u,int v){
    if(dep[u] < dep[v]) swap(u,v);
    int k = 0;
    while((1 << (k + 1)) <= dep[u]) ++k;
    for(int j = k;j >= 0;--j){
        if(dep[fa[u][j]] >= dep[v]) u = fa[u][j];
    }
    if(u == v) return u;
    for(int j = k;j >= 0;--j){
        if(fa[u][j] != fa[v][j]){
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}

const int maxnum = 100000;

int root[100005],cnt;

struct NODE{
    int l,r,maxn,pos;
    NODE(int ll = 0,int rr = 0,int maxnn = -1000000,int poss = 0){
        l = ll,r = rr,maxn = maxnn,pos = poss;
    }
}tree[20000005];

inline void pushup(int id){
    if(tree[id].l == 0) tree[id].l = ++cnt;
    if(tree[id].r == 0) tree[id].r = ++cnt;
    if(tree[tree[id].l].maxn >= tree[tree[id].r].maxn){
        tree[id].maxn = tree[tree[id].l].maxn;
        tree[id].pos = tree[tree[id].l].pos;
    }
    else{
        tree[id].maxn = tree[tree[id].r].maxn;
        tree[id].pos = tree[tree[id].r].pos;
    }
}

void update(int &id,int l,int r,int x,int num){
    if(id == 0) id = ++cnt;
    if(l == r){
        tree[id].maxn += num;
        tree[id].pos = l;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(tree[id].l,l,mid,x,num);
    else update(tree[id].r,mid + 1,r,x,num);
    pushup(id);
    return;
}

int ans[100005];//统计最终答案的数组

int merge(int p,int q,int l,int r){
    if(!p || !q) return p + q;
    if(l == r){
        tree[p].maxn += tree[q].maxn;
        return p;
    }
    int mid = (l + r) >> 1;
    tree[p].l = merge(tree[p].l,tree[q].l,l,mid);
    tree[p].r = merge(tree[p].r,tree[q].r,mid + 1,r);
    pushup(p);
    return p;
}


void search(int u,int last){
    for(int i = p[u];i != -1;i = e[i].nxt){
        int v = e[i].v;
        if(v == last) continue;
        search(v,u);
        root[u] = merge(root[u],root[v],1,maxnum);
    }
    ans[u] = tree[root[u]].pos;
    return;
}




int main(){
    //freopen("data.in","r",stdin);
    init();
    n = read();
    m = read();
    for(int i = 1;i < n;++i){
        int u,v;
        u = read();
        v = read();
        insert(u,v);
        insert(v,u);
    }
    dep[1] = 1;
    dfs(1,-1);
    for(int j = 1;(1 << j) <= n;++j){
        for(int i = 1;i <= n;++i) fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    for(int i = 1;i <= m;++i){
        int u,v,z;
        u = read();
        v = read();
        z = read();
        int LCA = lca(u,v);
        update(root[u],1,maxnum,z,1);
        update(root[v],1,maxnum,z,1);
        update(root[LCA],1,maxnum,z,-1);
        update(root[fa[LCA][0]],1,maxnum,z,-1);
    }
    search(1,-1);
    for(int i = 1;i <= n;++i) printf("%d\n",ans[i]);
    return 0; 
}

inline int read(){
    register int w = 0,flag = 1;
    register char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        w = (w << 3) + (w << 1) + (c ^ 48);
        c = getchar();
    }
    return w * flag;
}