首页 > 其他分享 >树上的差分

树上的差分

时间:2024-09-30 12:49:34浏览次数:9  
标签:cnt ++ 差分 次数 lca -- 树上

1. 点的差分

        求路径 u - v 上的点被经过的次数。

        cnt [ x ] 代表点 x 经过的次数。

        核心代码:

cnt[n]++;
cnt[v]++;
cnt[lca]--;
cnt[fa[lca]]--;

 2. 边的差分

        求 u - v 路径上每一条边经过的次数。

        cnt [ x ]:代表 x 向上的边经过的次数。

        核心代码:

cnt[u]++;
cnt[v]++;
cnt[lca]-=2;

标签:cnt,++,差分,次数,lca,--,树上
From: https://blog.csdn.net/Ryan_hsMax/article/details/142654332

相关文章

  • 【电磁学,向量场理论和Maxwell方程】二维FDTD(有限差分时域)解决完全电导体边界条件问题
     ......
  • 林史·树上的男爵 2 | 中
    3涛哥在树上的生活也并不总是一帆风顺的,毕竟是在野外,就算有时候找不到吃的或者水源,但这些危险比起大自然的种种威胁来,还是太过逊色了涛哥发现,并不是所有的线段树都能够比作水井,有些线段树积极的很,一有操作马上就会下放,但是有的线段树就像睡着了一样,使劲踹它两脚,它才像挤牙膏一样......
  • 树上问题学习
    T1题面有一个\(n\)个节点的树,根节点为\(1\),令叶子节点数为\(m\),叶子节点的权值为一个\(1\)到\(m\)的排列。Alice和Bob在树上玩游戏,两人从根节点开始,Alice先手的轮流的行走\(u\to\text{son}(u)\)的路径直到抵达叶子节点。叶子的权值为本次游戏的得分。Alice希望最大......
  • 林史·树上的男爵 2 | 上
    1在涛哥12岁之前,一切都像正常人平静的生活一般,涛哥正常地在房间里敲代码,正常地打模拟赛,正常地改题,正常地写闲话直到涛哥十二岁的时候,一切都变了那天上午,我完全没有意识到接下来的一天会发生什么,因为涛哥仍然像往常一样在房间里和我们聊天B先生出现了,说自己身为国家之重臣,需......
  • 最小割解决广义差分约束问题
    描述该做法解决了一类“广义差分约束”问题(当然名字是我自己取的),除了可以解决常见的求解\(A_1+c_1\geqA_2,A_2+c_2\geqA_3\dots\)问题外,还可以求解形如“如果\(A_1\geqc_1\),那么\(A_2\geqc_2\)”这样涉及条件逻辑运算的问题。另外,变量的取值还可以带权,即\(A_i\)取值\(......
  • 差分约束
    差分约束系统参考博客:oiwiki博客园差分约束系统定义差分约束系统是一种特殊的\(n\)元一次不等式组,它包含\(n\)个变量\(x_1,x_2,\dots,x_n\)以及\(m\)个约束条件,每个约束条件是由两个其中的变量做差构成的,形如\(x_i-x_j\leqc_k\),其中\(1\leqi,j\leqn,......
  • 远程升级频频失败?你可能忽略了模组差分包…
    去年开发的一个项目产品,用的是合宙4G-Cat.1低功耗模块Air780E。最近有客户反馈在乡村里频繁出现掉线的情况。通过换货、换SIM卡对比排查测试,发现只有去年5月22号采购的那批模块在客户环境附近会出现掉线的情况,而今年4月份采购的模块批次就不会掉线,很奇怪。我联系了对应负责的销售,了......
  • 亚诺德经典低失真差分ADC驱动器芯片——AD8138
    博主首拆华为三折叠MateXT:内部设计完胜iPhone16,零部件多是国产光刻机的“前世今生”推荐文章:本期是平台君和您分享的第78期内容NEWS新闻早知道今年的巴黎奥运会结束了,不仅是中国人,连无数外国人都情不自禁怀念起16年前的北京奥运会开幕式。在2008年,智能手机还没......
  • 一维差分和等差数列差分
    一维差分不支持边操作边查询对于数组a,定义其差分数组(differencearray)为i=0时,d[i]=a[0];i>0时,d[i]=a[i]-a[i-1];性质1:从左到右累加d中的元素,可以得到数组a。性质2:如下两个操作是等价的。区间操作:把a的子数组a[i,j]都加上x。单点操作:把d[i......
  • 树上差分+lca 黑暗的锁链
    //**太久不写了,感觉很难受。。。比赛最近打得也不好,课内任务又重,还要忙着做项目。何去何从。今天又写了一题,用了树上差分的知识。下面来整理整理。1.首先让我们学一下lca(最小公共父节点) 我用的是倍增来求的。总共其实就是两步:dfs打ST表预处理每个点的上面节点 lca求两......