当前位置: 首页 > news >正文

树上莫队

欧拉序树上莫队

通过欧拉序把树上莫队转化成序列莫队。

这里的欧拉序只的是 \(dfs\) 刚遍历到的时候加入点,遍历完整颗子树的时候再加入这个点。设 \(u\) 第一次出现的位置是 \(f[u]\),第二次出现的位置是 \(g[u]\),那么当我要求 \(u\)\(v\) 的信息时,在 \([g[u],f[v]]\) 这段区间中,链上的点除了 \(lca\) 可能不存在,其他点都只会出现一次。而不在链上的点,要么出现零次,要么出现两次。

为什么呢?首先不在 \(lca\) 子树里的点只会出现零次。其次在子树里的但不在链上的点,观察上图,会形成一颗颗子树“挂”在链上。子树有可能在 \(g[u]\) 之前遍历完了,那么都出现零次,有可能在 \(g[u]\) 之后遍历,那么都出现两次。而在链上的点,第一次出现的位置一定在 \(g[u]\) 之前,第二次出现的位置一定在 \(g[u]\) 之后,所以会出现一次。

然后你只要判一下 \(u\) 是否等于 \(lca(u,v)\) 就行了,如果不等于你还要加上 \(lca\) 处的贡献。

P4074 [WC2013] 糖果公园

用欧拉序把树上带修莫队变成序列带修莫队就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
vector<int>e[N];
int n,m,sq,Q,tot,res,a[N],b[N],c[N],p[N],s[N],bl[N],pos[N],cnt[N],vis[N];
int id,d[N],f[N],g[N],ans[N],st[N][25];
struct node{int l,r,t,id;
}q[N];
bool cmp(node x,node y){return bl[x.l]^bl[y.l]?x.l<y.l:bl[x.r]^bl[y.r]?x.r<y.r:x.t<y.t;}
void dfs(int u,int fa)
{f[u]=++id,pos[id]=u,d[u]=d[fa]+1,st[u][0]=fa;for(int v:e[u])if(v!=fa)dfs(v,u);g[u]=++id,pos[id]=u;return;
}
int lca(int x,int y)
{if(d[x]<d[y])swap(x,y);for(int i=20;i>=0;i--)if(d[st[x][i]]>=d[y])x=st[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];return st[x][0];
}
void add(int k,int s)
{res-=a[c[k]]*b[cnt[c[k]]];cnt[c[k]]-=(vis[k]*2-1);res+=a[c[k]]*b[cnt[c[k]]];vis[k]=(vis[k]+2+s)%2;return;
}
signed main()
{scanf("%lld%lld%lld",&n,&m,&Q);for(int i=1;i<=m;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]),b[i]+=b[i-1];for(int i=1,u,v;i<n;i++)scanf("%lld%lld",&u,&v),e[u].push_back(v),e[v].push_back(u);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);dfs(1,0),sq=pow(id,2.0/3.0);for(int i=1;i<=id;i++)bl[i]=i%sq==1?bl[i-1]+1:bl[i-1];for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];for(int i=1,op,x,y;i<=Q;i++){scanf("%lld%lld%lld",&op,&x,&y);if(op==0)p[i-tot]=x,s[i-tot]=y;else {if(f[x]>f[y])swap(x,y);q[++tot]={lca(x,y)==x?f[x]:g[x],f[y],i-tot,tot};}}sort(q+1,q+1+tot,cmp);for(int i=1,L=1,R=0,t=0;i<=tot;i++){while(L>q[i].l)add(pos[--L],1);while(R<q[i].r)add(pos[++R],1);while(L<q[i].l)add(pos[L++],-1);while(R>q[i].r)add(pos[R--],-1);while(t<q[i].t){++t;if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],-1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],-1);swap(c[p[t]],s[t]); if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],1);}while(t>q[i].t){if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],-1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],-1);swap(c[p[t]],s[t]);if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],1);--t;}if(pos[q[i].l]!=lca(pos[q[i].l],pos[q[i].r]))add(lca(pos[q[i].l],pos[q[i].r]),1),ans[q[i].id]=res,add(lca(pos[q[i].l],pos[q[i].r]),-1);else ans[q[i].id]=res;}for(int i=1;i<=tot;i++)printf("%lld\n",ans[i]);return 0;
}
http://www.hskmm.com/?act=detail&tid=14788

相关文章:

  • 比余额宝收益高的低风险短期理财工具-银行同业存单
  • 陇剑杯2025 决赛-ShellDecoder
  • Springcloud gateway笔记
  • AT_arc122_e [ARC122E] Increasing LCMs
  • C++ 锁
  • 飞书对程序员下手了,0 代码生成各类系统!!(附保姆级项目实战教程)
  • Adaptix C2:跨平台渗透测试与对抗仿真框架
  • 国标GB28181软件EasyGBS网页直播平台在邮政快递场景的落地与应用
  • sql统计一个字段各个值各有多个个的方法
  • WBS、甘特图、关键路径……项目计划的五大核心概念一文全懂
  • 智启新程:哲讯科技引领SAP ERP实施新范式
  • 移动端性能监控探索:鸿蒙 NEXT 探针架构与技术实现
  • 哲讯科技:以数智之力,铸就企业SAP ERP实施新典范
  • PR曲线绘制
  • 5台电脑怎么同步文件最安全高效?别再只知道用局域网共享了!
  • 关于CompatibilityHID例程的使用
  • SystemVerilog 代码风格指南
  • 赋能智慧化工:无锡哲讯科技SAP解决方案,构筑安全、合规与高效的数字新底座
  • 芯之所向,智造未来:无锡哲讯科技赋能芯片行业的高效管理与数字革新
  • UART、I2C、SPI:三种常见通信协议的区别
  • Day05---数据类型的转换
  • 个人项目——论文查重
  • 效率党的图片处理新选择:滴答修——在线全能工具箱,免费且强大
  • GPU0与GPU1
  • 对接全球股票市场K线数据实战
  • 9.23
  • centos安装docker和Jenkins
  • 硬件检测神器 HWiNFO:全组件监控 + 多系统兼容,免费无广告,运维 / 评测必备
  • Qt - 音频采集程序
  • 923-