【HDU3966】Aragorn's Story(樹鍊剖分+線段樹)

記錄一個菜逼的成長。。

轉自ACdreamers并稍加改動

樹鍊剖分用一句話概括就是：把一棵樹剖分為若幹條鍊，然後利用資料結構(樹狀數組，SBT，Splay，線段樹等等)去維護每一條鍊，複雜度為O(logn)

那麼，樹鍊剖分的第一步當然是對樹進行輕重邊的劃分。

定義size(x)為以x為根的子樹節點個數，令v為u的兒子中size值最大的節點，那麼(u,v)就是重邊，其餘邊為輕邊。

當然，關于這個它有兩個重要的性質：

(1)輕邊(u,v)中，size(v)<=size(u)/2

(2)從根到某一點的路徑上，不超過logn條輕邊和不超過logn條重路徑。

當然，剖分過程分為兩次dfs，或者bfs也可以。

如果是兩次dfs，那麼第一次dfs就是找重邊，也就是記錄下所有的重邊。

然後第二次dfs就是連接配接重邊形成重鍊，具體過程就是：以根節點為起點，沿着重邊向下拓展，拉成重鍊，不在目前重鍊上的節點，都以該節點為起點向下重新拉一條重鍊。

剖分完畢後，每條重鍊相當于一段區間，然後用資料結構去維護，把所有重鍊首尾相接，放到資料結構上，然後維護整體。

在這裡，當然有很多數組，現在我來分别介紹它們的作用：

siz[]數組，用來儲存以x為根的子樹節點個數

top[]數組，用來儲存目前節點的所在鍊的頂端節點

son[]數組，用來儲存重兒子

dep[]數組，用來儲存目前節點的深度

fa[]數組，用來儲存目前節點的父親

tid[]數組，用來儲存樹中每個節點剖分後的新編号

pos[]數組，用來儲存目前節點線上段樹中的位置

那麼，我們現在可以根據描述給出剖分的代碼：

第一次dfs：記錄所有的重邊

void dfs1(int u,int father,int d)
{
    dep[u] = d;
    fa[u] = father;
    siz[u] = ;
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != father)
        {
            dfs1(v,u,d+);
            siz[u] += siz[v];
            if(son[u] == - || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}
           

第二次dfs：連重邊成重鍊

void dfs2(int u,int tp)
{
    top[u] = tp;
    tid[u] = ++num;
    pos[tid[u]] = u;
    if(son[u] == -) return;
    dfs2(son[u],tp);
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != son[u] && v != fa[u])
            dfs2(v,v);
    }
}
           

題目連結

題目大意：

給一棵樹，并給定各個點權的值，然後有3種操作：

I C1 C2 K: 把C1與C2的路徑上的所有點權值加上K

D C1 C2 K：把C1與C2的路徑上的所有點權值減去K

Q C：查詢節點編号為C的權值

PS：第一道樹剖題。

樹鍊剖分後用線段樹進行維護即可。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))
#define lson t<<1,l,mid
#define rson t<<1|1,mid+1,r
#define seglen(t) (node[(t)].r-node[(t)].l+1)
typedef long long LL;
const int maxn =  + ;
int head[maxn],cnt;
struct Edge{
    int to,next;
}edge[maxn<<];
void add(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int num;
int val[maxn],siz[maxn],dep[maxn],son[maxn];
int top[maxn],tid[maxn],pos[maxn],fa[maxn];
void init()
{
    cl(head,-);cl(son,-);
    cnt = num = ;
}
///樹鍊剖分部分
void dfs1(int u,int father,int d)
{
    dep[u] = d;
    fa[u] = father;
    siz[u] = ;
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != father)
        {
            dfs1(v,u,d+);
            siz[u] += siz[v];
            if(son[u] == - || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}

void dfs2(int u,int tp)
{
    top[u] = tp;
    tid[u] = ++num;
    pos[tid[u]] = u;
    if(son[u] == -) return;
    dfs2(son[u],tp);
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != son[u] && v != fa[u])
            dfs2(v,v);
    }
}
///線段樹部分
struct Node{
    int l,r,sum,lazy;
}node[maxn<<];
void pushup(int t)
{
    node[t].sum = max(node[t<<].sum ,node[t<<|].sum);
}
void pushdown(int t)
{
    if(node[t].lazy){
        int tmp = node[t].lazy;
        node[t<<].lazy += tmp;
        node[t<<|].lazy += tmp;
        node[t<<].sum += seglen(t<<)*tmp;
        node[t<<|].sum += seglen(t<<|)*tmp;
        node[t].lazy = ;
    }
}
void build(int t,int l,int r)
{
    node[t].l = l;
    node[t].r = r;
    node[t].lazy = ;
    if(l == r){
        node[t].sum = val[pos[l]];
        return ;
    }
    int mid = (l + r) >> ;
    build(lson);
    build(rson);
    pushup(t);
}
void update(int t,int l,int r,int v)
{
    if(l <= node[t].l && r >= node[t].r){
        node[t].sum += seglen(t) * v;
        node[t].lazy += v;
        return ;
    }
    pushdown(t);
    int mid = (node[t].l + node[t].r) >> ;
    if(l <= mid)update(t<<,l,r,v);
    if(r > mid)update(t<<|,l,r,v);
    pushup(t);
}
int query(int t,int c)
{
    if(node[t].l == node[t].r){
        return node[t].sum;
    }
    pushdown(t);
    int mid = (node[t].l + node[t].r) >> ;
    int ret;
    if(c <= mid)ret = query(t<<,c);
    else ret = query(t<<|,c);
    pushup(t);
    return ret;
}
void change(int x,int y,int val)
{
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        update(,tid[top[x]],tid[x],val);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    update(,tid[x],tid[y],val);
}
int main()
{
    char ope[];
    int n,m,p,x;
    while(~scanf("%d%d%d",&n,&m,&p)){
        init();
        for( int i = ; i <= n; i++ ){
            scanf("%d",val+i);
        }
        for( int i = ; i < m; i++ ){
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dfs1(,,);
        dfs2(,);
        build(,,n);
        while(p--){
            scanf("%s",ope);
            if(ope[] == 'Q'){
                scanf("%d",&x);
                printf("%d\n",query(,tid[x]));
            }
            else {
                int u,v;
                scanf("%d%d%d",&u,&v,&x);
                if(ope[] == 'D')x = -x;
                change(u,v,x);
            }
        }
    }
    return ;
}