【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 ;
}