树链剖分

void dfs1(int u,int fa,int depth)
{
    dep[u]=depth;
    f[u]=fa;sz[u]=1;son[u]=-1;
    for(int i=first[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].e;
        if(v==fa) continue;
        dfs1(v,u,depth+1);
        up[v]=edge[i].w;
        sz[u]+=sz[v];
        if(son[u]==-1||sz[son[u]]<sz[v]) son[u]=v;
    }
}

void dfs2(int u,int tp)
{
    top[u]=tp;
    id[u]=++mark;
    p[mark]=u;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=first[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].e;
        if(v==f[u]||v=son[u]) continue;
        dfs2(v,v);
    }
}

void change(int u,int v,int w)
{
    int tu=top[u];
    int tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv])
        {
            swap(tu,tv);
            swap(u,v);
        }
        update(id[tu],id[u],1,n,1,w);
        u=f[tu];
        tu=top[u];
    }
    if(u==v) return;//根据是边权还是点权修改
    if(dep[u]<dep[v]) swap(u,v);
    update(id[son[v]],id[u],1,n,1,w);
}