JZOJ 2256【ZJOI2008】樹的統計

Description

　一棵樹上有n個節點，編号分别為1到n，每個節點都有一個權值w。

　　我們将以下面的形式來要求你對這棵樹完成一些操作：

　　I. CHANGE u t : 把結點u的權值改為t

　　II. QMAX u v: 詢問從點u到點v的路徑上的節點的最大權值

　　III. QSUM u v: 詢問從點u到點v的路徑上的節點的權值和

　　注意：從點u到點v的路徑上的節點包括u和v本身

Analysis

本蒟蒻的第一道樹剖。

不多說，裸題一道。

Key Code

int solve(int u,int v,bool bz)
{
    int ans=bz?-N:,x;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        x=top[v];
        if(bz) ans=max(ans,find(,,m,w[x],w[v],bz));
        else ans+=find(,,m,w[x],w[v],bz);
        v=fa[x];
    }
    if(dep[u]>dep[v]) swap(u,v);
    if(bz) ans=max(ans,find(,,m,w[u],w[v],bz));
    else ans+=find(,,m,w[u],w[v],bz);
    return ans;
}