首页 > 其他分享 >轻重链剖分板子

轻重链剖分板子

时间:2023-01-26 08:55:25浏览次数:42  
标签:链剖分 sz int father top tr 板子 dep 轻重

// Luogu P3384 【模板】轻重链剖分/树链剖分
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define lc u<<1
#define rc u<<1|1
using namespace std;

typedef long long LL;
const int N=100010;
int n,m,a,b,root,p;
int w[N];
vector<int> e[N];
int fa[N],dep[N],sz[N],son[N];
int top[N],id[N],nw[N],cnt;

void dfs1(int u,int father){//搞fa,dep,sz,son
  fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
  for(int v:e[u]){
    if(v==father) continue;
    dfs1(v,u);
    sz[u]+=sz[v];
    if(sz[son[u]]<sz[v]) son[u]=v; 
  }
}
void dfs2(int u,int t){//搞top,id,nw
  top[u]=t,id[u]=++cnt,nw[cnt]=w[u];
  if(!son[u]) return;
  dfs2(son[u],t);
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v);
  }
}

struct tree{
  int l,r; 
  LL add,sum;
}tr[N*4]; //线段树

void pushup(int u){
  tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int u){
  if(tr[u].add){
    tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1);
    tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1);
    tr[lc].add+=tr[u].add;
    tr[rc].add+=tr[u].add;
    tr[u].add=0;
  }
}
void build(int u,int l,int r){
  tr[u]={l,r,0,nw[r]};
  if(l==r) return;
  int mid=l+r>>1;
  build(lc,l,mid),build(rc,mid+1,r);
  pushup(u);
}
void update(int u,int l,int r,int k){
  if(l<=tr[u].l&&r>=tr[u].r){
    tr[u].add+=k;
    tr[u].sum+=k*(tr[u].r-tr[u].l+1);
    return;
  }
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  if(l<=mid) update(lc,l,r,k);
  if(r>mid) update(rc,l,r,k);
  pushup(u);
}
void update_path(int u,int v,int k){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    update(1,id[top[u]],id[u],k);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  update(1,id[v],id[u],k);//最后一段
}
void update_tree(int u,int k){
  update(1,id[u],id[u]+sz[u]-1,k);
}
LL query(int u,int l,int r){
  if(l<=tr[u].l&&r>=tr[u].r)return tr[u].sum;
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  LL res=0;
  if(l<=mid) res+=query(lc,l,r);
  if(r>mid) res+=query(rc,l,r);
  return res;
}
LL query_path(int u,int v){
  LL res=0;
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]]) swap(u,v);
    res+=query(1,id[top[u]],id[u]);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v]) swap(u,v);
  res+=query(1,id[v],id[u]);//最后一段
  return res;
}
LL query_tree(int u){
  return query(1,id[u],id[u]+sz[u]-1);
}
int main(){
  scanf("%d%d%d%d",&n,&m,&root,&p);
  for(int i=1; i<=n; i++) 
    scanf("%d",&w[i]);
  for(int i=0; i<n-1; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs1(root,0);
  dfs2(root,root);//把树拆成链
  build(1,1,n); //用链建线段树
  while(m--){
    int t,u,v,k;
    scanf("%d%d",&t,&u);
    if(t==1){
      scanf("%d%d",&v,&k);
      update_path(u,v,k);
    }
    else if(t==3){
      scanf("%d",&k);
      update_tree(u,k);
    }
    else if(t==2){
      scanf("%d",&v);
      printf("%d\n",query_path(u,v)%p);
    }
    else printf("%d\n",query_tree(u)%p);
  }
  return 0;
}

来自dx123

标签:链剖分,sz,int,father,top,tr,板子,dep,轻重
From: https://www.cnblogs.com/CYLSY/p/17067550.html

相关文章

  • 2568. 树链剖分
    2568.树链剖分原题链接思路:先将一颗树进行树链剖分,再将它的dfs序求出来利用dfs序将线段树模拟出来(build出来)再将输入的路径进行切割导入线段树处理,直到两个元素......
  • Qemu查询支持的芯片的板子、CPU型号
    1.查看支持的板子(即SOC):qemu-system-xxx-Mhelp例如:想查询支持的arm芯片的板子:qemu-system-arm-Mhelp想查询支持的PowerPC(32位)芯片的板子:qemu-system-ppc-Mhel......
  • 【组会】2023_1_13 看openradar 整理板子v1
    在学校采的数据,计算出来正确的数据大小应该是102400KB,但采下来的数据是51200KB(正确数据的1/2)(所以以后每次采数据之后要先手算一下bin文件大小对不对看openradar代码,......
  • 算法学习笔记(6): 树链剖分
    树链剖分树链剖分是一个很神奇,但是在树上可以完成一些区间操作问题简单来说,就是把一棵树分成一条条的链,通过维护链上的信息来维护整棵树的信息基础知识可以参考我的另外......
  • AD9144-FMC-EBZ ADI数据转接板四通道数模转换器评估板子模块
    ......
  • AD9144-FMC-EBZ ADI数据转接板四通道数模转换器评估板子模块
    ......
  • 旅行[板子题]
    链接:https://ac.nowcoder.com/acm/contest/50380/D来源:牛客网小z放假了,准备到RRR城市旅行,其中这个城市有N个旅游景点。小z时间有限,只能在三个旅行景点进行游玩。小明租了......
  • 树链剖分 学习笔记
    树链剖分是一种思想,可以用来通过给树中每个点重新编号,从而让树中任意一条路径转化成\(O(logn)\)段连续区间(链)。树中任意一条路径均可以变成不超过\(logn\)段连续区间......
  • OpenOCD如何通过stlink直接下载程序到stm32板子(已解决)
    首先,关于OpenOCD的入门介绍,以及如何调试,看我这篇文章:​​嵌入式IDE原理OpenOCD介绍以及stlink如何连接stm32板子_标biao的博客-由于OpenOCD一旦连接上,会自动进入3种端口监......
  • P2146 [NOI2015] 软件包管理器 树链剖分
    //题目大意:给定一棵树,树上的每个节点是一个软件,现在给出如下两个指令,install与uninstall,//如果需要installx号软件,那么我需要安装他到根节点之间的所有软件;如......