Bzoj1036 樹鏈剖分基礎題

樹鏈剖分的基礎題

因為復習到了這個部分突然發現竟然沒有題解所以現在補一個。。

一些基礎的東西。。。

重兒子：siz[u]為v的子節點中siz值最大的，那麼u就是v的重兒子。
輕兒子：v的其它子節點。
重邊：點v與其重兒子的連邊。
輕邊：點v與其輕兒子的連邊。
重鏈：由重邊連成的路徑。
輕鏈：輕邊。

然後簡單的用兩次dfs計算出每個節點的father，deep，size， son，w，top

其他簡單的就不說了

w表示的是當前節點與其付清節點的連邊在線段樹中的位置

top表示的是當前節點所在的鏈的頂端的節點

其他的東西都比較簡單，代碼可以著重看下查詢那段，因為不用求LCA所以不錯。。。

#include
#include
#include
#include
#define inf 0x7fffffff/4
#define MAX 123333
#define rep(i,j,k) for(int i=j;i<=k;i++)
 
using namespace std;
 
int n,m,father[MAX],deep[MAX],size[MAX],w[MAX],value[MAX],head[2*MAX];
int next[2*MAX],to[2*MAX],top[MAX],Max[MAX],sum[MAX];
int b[MAX],son[MAX],num=0,tot=0,done[MAX];
int l[4*MAX],r[4*MAX];
 
void add(int from,int To)
{
    to[++tot]=To;
    next[tot]=head[from];
    head[from]=tot;
}
 
void dfs(int fa,int x,int dep)
{
    deep[x]=dep;
    size[x]=1;
    son[x]=0;
    for(int i=head[x];i;i=next[i])
        if(to[i]!=fa)
        {
            father[to[i]]=x;
            dfs(x,to[i],dep+1);
            if(size[to[i]]>size[son[x]])
                son[x]=to[i];
            size[x]+=size[to[i]];
        }
}
 
void dfs2(int tp,int x)
{
    w[x]=++num;
    b[num]=value[x];
    top[x]=tp;
    if(son[x])
        dfs2(top[x],son[x]);
    for(int i=head[x];i;i=next[i])
        if(to[i]!=son[x]&&to[i]!=father[x])
            dfs2(to[i],to[i]);
}
 
inline void up(int x)
{
    if(l[x]==r[x])
        return;
    Max[x]=max(Max[2*x],Max[2*x+1]);
    sum[x]=sum[2*x]+sum[2*x+1];
}
 
inline void build(int x,int la,int ra)
{
    l[x]=la;
    r[x]=ra;
    if(la==ra)
    {
        Max[x]=sum[x]=b[la];
        return;
    }
    int mid=(la+ra)>>1;
    build(2*x,la,mid);
    build(2*x+1,mid+1,ra);
    up(x);
}
 
void change(int x,int pos,int number)
{
    if(l[x]==r[x]&&l[x]==pos)
    {
        Max[x]=sum[x]=number;
        return;
    }
    int mid=(l[x]+r[x])>>1;
    if(pos<=mid)
        change(2*x,pos,number);
    else
        change(2*x+1,pos,number);
    up(x);
}
 
int query_max(int x,int la,int ra)
{
    if(l[x]>ra||r[x]>1;
    return max(query_max(2*x,la,ra),query_max(2*x+1,la,ra));
}
 
inline int ask_max(int x,int y)
{
    int ret=-inf;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]ra||r[x]