洛谷 - P3384 轻重链剖分

线段树 树链剖分
题解
发布日期:   2020-03-04
更新日期:   2020-03-27
文章字数:   1.8k
阅读时长:   8 分
阅读次数:  

传送门：洛谷 - P3384

题目描述

如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

  1. 格式： $1$ $x$ $y$ $z$ 表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$
  2. 格式： $2$ $x$ $y$ 表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和
  3. 格式： $3$ $x$ $z$ 表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$
  4. 格式： $4$ $x$ 表示求以 $x$ 为根节点的子树内所有节点值之和

输入描述

第一行包含 $4$ 个正整数 $N$,$M$,$R$,$P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）
接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值
接下来 $N-1$ 行每行包含两个整数 $x$,$y$表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）
接下来 $M$ 行每行包含若干个正整数，每行表示一个操作

输出描述

输出答案

概念

  • 重儿子：对于每一个非叶子节点，它的儿子中 以那个儿子为根的子树节点数最大的儿子 为该节点的重儿子
  • 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
    叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
  • 重边：一个父亲连接他的重儿子的边称为重边
  • 轻边：剩下的即为轻边
  • 重链：相邻重边连起来的 连接一条重儿子 的链叫重链
    • 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
    • 每一条重链以轻儿子为起点

dfs1（确定重儿子）

这个dfs要处理几件事情：

  • 标记每个点的深度dep
  • 标记每个点的父亲fa
  • 标记每个非叶子节点的子树大小（含它自己）
  • 标记每个非叶子节点的重儿子编号son
void dfs1(int u, int f) {
    fa[u] = f; //记录父亲
    dep[u] = dep[f] + 1; //更新深度
    siz[u] = 1; //子树大小
    int maxsize = -1; //最大子树大小
    for (auto v : e[u]) {
        if (v == f)continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > maxsize) {  //更新重儿子
            son[u] = v;
            maxsize = siz[v];
        }
    }
}

dfs2（标记时间戳）

这个dfs要做以下事情：

  • 标记每个点的时间戳
  • 建立一个新的权值数组
  • 确定每个重链的顶端
void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++tim;
    w[tim] = a[u];
    if (!son[u])   //没有重儿子说明没有儿子了
        return ;
    dfs2(son[u], t); //先处理重儿子
    for (auto v : e[u]) {
        if (v == son[u] || v == fa[u])
            continue;
        dfs2(v, v); //轻儿子作为顶端
    }
}

处理问题

在链上的时间戳是连续的，所以区间问题可以用线段树维护

有两种情况：

  1. 两个点不在一条链上
  2. 两个点在一条链上

对与第一种情况：

  • 设$x$为深度较大的那个点
  • $ans$加上$x$到$x$顶端的点权和
  • $x$更新为它的顶端

不断进行上述操作，直到两个点在同一链上
复杂度为$O(log^2n)$

对于第二种情况：

  • 直接进行区间操作就行了

复杂度为$O(logn)$

样例输入

5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

样例输出

2
21

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

struct node {
    int l,r,sum,mid,len,lazy;
} tree[N<<2];

int a[N],mod;
vector<int>e[N];
int fa[N],dep[N],son[N],siz[N],tim,dfn[N],top[N],w[N];

void dfs1(int u,int f) {
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    int maxsize=-1;
    for(auto v:e[u]) {
        if(v==f)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxsize) {
            son[u]=v;
            maxsize=siz[v];
        }
    }
}

void dfs2(int u,int t) {
    top[u]=t;
    dfn[u]=++tim;
    w[tim]=a[u];
    if(!son[u])
        return ;
    dfs2(son[u],t);
    for(auto v:e[u]) {
        if(v==son[u]||v==fa[u])
            continue;
        dfs2(v,v);
    }
}

void pp(int x) {
    tree[x].sum=(tree[ls].sum+tree[rs].sum)%mod;
}

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    tree[x].len=r-l+1;
    if(l==r) {
        tree[x].sum=w[l];
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}

void pd(int x) {
    if(tree[x].lazy) {
        tree[ls].lazy=(tree[x].lazy+tree[ls].lazy)%mod;
        tree[rs].lazy=(tree[x].lazy+tree[rs].lazy)%mod;
        tree[rs].sum=(tree[rs].sum+tree[x].lazy*tree[rs].len)%mod;
        tree[ls].sum=(tree[ls].sum+tree[x].lazy*tree[ls].len)%mod;
        tree[x].lazy=0;
    }
}

void update(int x,int l,int r,int v) {
    if(l<=tree[x].l && tree[x].r<=r) {
        tree[x].sum=(tree[x].sum+v*tree[x].len)%mod;
        tree[x].lazy=(tree[x].lazy+v)%mod;
        return ;
    }
    pd(x);
    int mid=tree[x].mid;
    if(l<=mid)
        update(ls,l,r,v);
    if(r>mid)
        update(rs,l,r,v);
    pp(x);
}

int query(int x,int l,int r) {
    if(l<=tree[x].l&&tree[x].r<=r) {
        return tree[x].sum%mod;
    }
    pd(x);
    int mid=tree[x].mid;
    int ans=0;
    if(l<=mid)
        ans+=query(ls,l,r)%mod;
    if(r>mid)
        ans+=query(rs,l,r)%mod;
    return ans%mod;
}

void cqson(int x,int y,int v) {
    v%=mod;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        update(1,dfn[top[x]],dfn[x],v);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update(1,dfn[x],dfn[y],v);
}

int qqson(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ret += query(1,dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ret += query(1,dfn[x], dfn[y]);
    return ret % mod;
}

void cson(int x, int v) {
    update(1,dfn[x], dfn[x] + siz[x] - 1, v);
}

int qson(int x) {
    return query(1,dfn[x], dfn[x] + siz[x] - 1);
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m,r;
    cin>>n>>m>>r>>mod;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(r,r);
    dfs2(r,r);
    build(1,1,n);
    while(m--) {
        int opt, x, y, z;
        cin>>opt;
        switch (opt) {
            case 1:
                cin>>x>>y>>z;
                cqson(x, y, z);
                break;
            case 2:
                cin>>x>>y;
                cout<<qqson(x,y)<<endl;
                break;
            case 3:
                cin>>x>>z;
                cson(x,z);
                break;
            case 4:
                cin>>x;
                cout<<qson(x)<<endl;
                break;
        }
    }


    return 0;
}
文章作者: 小凡
文章链接: http://yoursite.com/2020/03/04/luogu3384/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 小凡 !
线段树 树链剖分
赏
评论
  目录
隐藏
{% if theme.sakura.enable %}{% endif %}