Heavy-Light Decomposition

struct HeavyLightDecomposition
{
    static const int __=500005;
    int pre[__],siz[__],dep[__];
    int top[__],heavy[__],lson[__],rson[__];
    int n,root,idx;
    ll val[__];
    vector<int>G[__];

    HeavyLightDecomposition():root(1) {}

    void build(int _n)
    {
        n=_n,idx=0;
        dfs(root,0,1),slpf(root,0,root);
        fup(i,1,n)a[lson[i]]=val[i];
        T.build(n);
    }

    void add_edge(int x,int y)
    {
        G[x].pb(y);
    }

    int dfs(int x,int fa,int depth)
    {
        dep[x]=depth,pre[x]=fa;
        int res=1,maxx=0;
        fup(i,0,sz(G[x])-1)
        {
            if(G[x][i]==fa)continue;
            int t=dfs(G[x][i],x,depth+1);
            if(t>maxx)maxx=t,heavy[x]=G[x][i];
            res+=t;
        }
        return siz[x]=res;
    }

    void slpf(int x,int fa,int tp)
    {
        lson[x]=++idx,top[x]=tp;
        if(heavy[x])slpf(heavy[x],x,tp);
        fup(i,0,sz(G[x])-1)
            if(G[x][i]!=fa && G[x][i]!=heavy[x])
                slpf(G[x][i],x,G[x][i]);
        rson[x]=idx;
    }

    ll get_sum(int x,int y)
    {
        ll ans=0;
        for(;top[x]!=top[y];x=pre[top[x]])
        {
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            ans+=T.get_val(lson[top[x]],lson[x]);
        }
        if(dep[x]>dep[y])swap(x,y);
        ans+=T.get_val(lson[x],lson[y]);
        return ans;
    }

    void add(int x,int y,ll val)
    {
        for(;top[x]!=top[y]; x=pre[top[x]])
        {
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            T.add(lson[top[x]],lson[x],val);
        }
        if(dep[x]>dep[y])swap(x,y);
        T.add(lson[x],lson[y],val);
    }

    //子树加
    void add(int x,ll val){T.add(lson[x],rson[x],val);}

    //子树求和

    ll get_sum(int x){return T.get_val(lson[x],rson[x]);}

    int lca(int x,int y)
    {
        for(;top[x]!=top[y];x=pre[top[x]])
            if(dep[top[x]]<dep[top[y]])swap(x,y);
        if(dep[x]>dep[y])swap(x,y);
        return x;
    }

    void clear(){memset(heavy,0,sizeof(heavy));}
}hld;

题目链接:Query on a tree

树链剖分(权值在边上)[单点修改 询问区间最大值]:

int a[10005];

struct node
{
    int tl,tr,val;
} tree[40020];

inline void pushup(int id)
{
    tree[id].val=max(tree[id<<1].val,tree[id<<1|1].val);
}

inline void build(int id,int tl,int tr)
{
    tree[id].tl=tl,tree[id].tr=tr;
    if(tl==tr)tree[id].val=a[tl];
    else
    {
        int tm=(tl+tr)>>1;
        build(id<<1,tl,tm);
        build(id<<1|1,tm+1,tr);
        pushup(id);
    }
}

inline void update(int id,int wz,int val)
{
    int tl=tree[id].tl,tr=tree[id].tr;
    if(tl==wz && wz==tr)tree[id].val=val;
    else
    {
        int tm=(tl+tr)>>1;
        if(tm>=wz)update(id<<1,wz,val);
        else update(id<<1|1,wz,val);
        pushup(id);
    }
}

inline int getval(int id,int ql,int qr)
{
    int tl=tree[id].tl,tr=tree[id].tr;
    if(ql<=tl && tr<=qr)return tree[id].val;
    int tm=(tl+tr)>>1,res1=0,res2=0;
    if(tm>=ql)res1=getval(id<<1,ql,qr);
    if(tm<qr)res2=getval(id<<1|1,ql,qr);
    return max(res1,res2);
}

struct edge
{
    int nex,id,val;
    edge(int nex,int id,int val):
        nex(nex),id(id),val(val) {}
};

int pre[10005],siz[10005],dep[10005];
int top[10005],edge_id[10005],heavy[10005];
int val[10005],ith[10005];
int idx=1;
vector<edge>G[10005];

inline void init(void)
{
    idx=1;
    memset(a,0,sizeof(a));
    memset(ith,0,sizeof(ith));
    memset(val,0,sizeof(val));
    memset(top,0,sizeof(top));
    memset(pre,0,sizeof(pre));
    memset(siz,0,sizeof(siz));
    memset(dep,0,sizeof(dep));
    memset(heavy,0,sizeof(heavy));
    memset(tree,0,sizeof(tree));
    memset(edge_id,0,sizeof(edge_id));
}

int dfs(int x,int fa,int depth)
{
    dep[x]=depth,pre[x]=fa;
    int res=1,maxx=0;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i].nex;
        if(nex==fa)continue;
        int t=dfs(nex,x,depth+1);
        ith[G[x][i].id]=nex;
        val[nex]=G[x][i].val;
        if(t>maxx)maxx=t,heavy[x]=nex;
        res+=t;
    }
    return siz[x]=res;
}

void slpf(int x,int fa,int tp)
{
    int len=G[x].size();
    if(pre[x])edge_id[x]=idx++;
    top[x]=tp;
    if(heavy[x])slpf(heavy[x],x,tp);
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i].nex;
        if(nex==fa)continue;
        if(nex!=heavy[x])
            slpf(nex,x,nex);
    }
}

int getmax(int x,int y)
{
    int ans=0,res;
    for(; top[x]!=top[y]; x=pre[top[x]])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=getval(1,edge_id[top[x]],edge_id[x]);
        if(res>ans)ans=res;
    }
    if(dep[x]==dep[y])return ans;
    if(dep[x]>dep[y])swap(x,y);
    if(edge_id[heavy[x]]>edge_id[y])swap(x,y);
    res=getval(1,edge_id[heavy[x]],edge_id[y]);
    return max(res,ans);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n-1; i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            G[x].push_back(edge(y,i,z));
            G[y].push_back(edge(x,i,z));
        }
        dfs(1,0,1);
        slpf(1,0,1);
        for(int i=1; i<=n; i++)
            if(pre[i])a[edge_id[i]]=val[i];
        build(1,1,n-1);
        while(1)
        {
            char op[10];
            int x,y;
            scanf("%s",op);
            if(op[0]=='D')break;
            scanf("%d%d",&x,&y);
            if(op[0]=='Q')printf("%d\n",getmax(x,y));
            if(op[0]=='C')update(1,edge_id[ith[x]],y);
        }
        printf("\n");
        for(int i=1; i<=n; i++)
            G[i].clear();
    }
    return 0;
}