首页 > 其他分享 >[学习笔记] 树上差分 - 图论

[学习笔记] 树上差分 - 图论

时间:2024-04-13 18:33:06浏览次数:23  
标签:图论 int 笔记 树链 flag 差分 权值 节点

前置知识:树,LCA,前缀和与差分

边差分

这个名字是在网上看到的,不理解为什么要叫这么一个名字,可能是因为它与 树链修改 有关。当然,用于 树链修改 单点查询 非常方便~

image

看这个图,该图是以点1为根进行DFS的。如果我们要把从3 -> 4这条树链上所有的点统统加上1,可以都转化为对到根节点的树链的操作,我们可以把3 -> 1全加上1,4 -> 1全加上1,发现2多加了1,1多加了2,所以2 - > 1减掉1,1 -> 1减掉1。这并不难想。但是如何实现把某一结点到根节点上所有的点进行权值加减呢?

联想到差分,我们可以分树链差分,对于3 -> 1链上的点,将这条链的开始(节点3)+1,将这条链的末尾(节点0)-1,最后查询时,把这个节点的子节点权值和自身权值相加即为最终权值。

image

画图太难用了!

看一道例题:[JLOI2014] 松鼠的新家

一道典型的树链修改 单点查询 + LCA题目。需要注意,我们在对每段路径进行操作的时候,前一个路径的尾端点与后一个路径的首端点多放了一个糖果,而且,最后一段路径的右端点是不用放糖果的,所以要统统减掉。

#include<bits/stdc++.h>
using namespace std;
#define min(x,y) (in[x]<in[y])?x:y
const int N = 3e5 + 1;
int n, ord[N], in[N], st[19][N], tot, w[N];
vector<int> G[N];
bitset<N> flag;
inline void dfs1(int k, int fa){
	st[0][in[k] = ++tot] = fa;
	for(int v : G[k]) if(!in[v]) dfs1(v, k);
}
inline void dfs2(int k){
	flag[k] = 1;
	for(int v : G[k]) if(!flag[v]) dfs2(v), w[k] += w[v];
}
inline int lca(int a, int b){
	if(a == b) return a;
	if((a = in[a]) > (b = in[b])) swap(a, b);
	int k = __lg(b-a++);
	return min(st[k][a], st[k][b-(1<<k)+1]);
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>ord[i];
	for(int i=1, a, b; i<n; ++i){
		cin>>a>>b;
		G[a].push_back(b), G[b].push_back(a);
	}
	dfs1(1, 0);
	for(int i=1; i<=__lg(n); ++i)
	for(int j=1; j<=n-(1<<i)+1; ++j)
		st[i][j] = min(st[i-1][j], st[i-1][j+(1<<i-1)]);
	for(int i=1; i<n; ++i){
		int a = ord[i], b = ord[i+1];
		int fa = lca(a, b);
//		printf("lca(%d, %d) = %d\n", a, b, fa);
		++w[a], ++w[b], --w[fa], --w[st[0][in[fa]]];
	}	
	dfs2(1);
	for(int i=1; i<=n; ++i){
		if(i != ord[1]) --w[i];
		cout<<w[i]<<'\n';
	}
	return 0;
}

标签:图论,int,笔记,树链,flag,差分,权值,节点
From: https://www.cnblogs.com/xiaolemc/p/18133193

相关文章

  • React笔记(一)
    基础型exportdefaultfunctionProfile(){return(<imgsrc="https://i.imgur.com/MK3eW3Am.jpg"alt="KatherineJohnson"/>)}默认 exportdefaultfunctionButton(){} importButtonfrom'./Button.js�......
  • 苍穹外卖学习笔记——第五天
    店铺营业状态设置Redis入门Redis简介Redis是一个基于内存的key-value结构数据库。Redis的特点基于内存存储,读写性能高。适合存储热点数据(热点商品、资讯、新闻)。企业应用广泛。Redis的网站官网:https://redis.io中文网:https://www.redis.net.cn/Redis的下载与安装......
  • FFmpeg开发笔记(十三)Windows环境给FFmpeg集成libopus和libvpx
    ​MP4是最常见的视频封装格式,在《FFmpeg开发实战:从零基础到短视频上线》一书的“1.2.3 自行编译与安装FFmpeg”介绍了如何给FFmpeg集成x264和x265两个库,从而支持H.264和H.265两种标准的编解码。视频的封装格式除了悠久的MP4和ASF之外,还有较新的WebM格式,该格式的音频编码主要采......
  • FFT 与 NTT 学习笔记
    【概念】点值:给定多项式\(f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\)和\(x_1\simx_m\),求\(f(x_1),f(x_2),\dots,f(x_m)\)。(\(m=n\))求点值的算法一般是\(O(n^2)\)的,但对于特殊的多项式,可以做到更快。插值:给定\((x_0,y_0),(x_1,y_1),\dots,(x_{n-1},y_{n-1})\),其中\(x_0\s......
  • 杜教筛学习笔记
    杜教筛学习笔记杜教筛被用于求解某一数论函数\(f\)的前缀和,即对于形如\(S(n)=\sum_{i=1}^nf(i)\)形式的函数\(S\),杜教筛能够在小于线性复杂度的复杂度内求解。算法思想尝试构造一个函数\(S\)的递推式。选择一个数论函数\(g\),那么根据狄利克雷卷积可以得到:\[\begin{ali......
  • 读所罗门的密码笔记18_大宪章
    1. 大宪章1.1. 1215年会议开启了一个艰难的谈判过程,充满了紧张和对权力与道德权威的争夺1.1.1. 这部宪章会赋予各方一系列的权力,对国王的自由裁量权进行制衡1.2. 《大宪章》还需要300多年的时间和多次迭代,才能成为财产权、公平税收、司法程序和政府最高法律的参考文件1.3......
  • SeleniumBase 制作WEB用户使用导览,并导出 JS-使用笔记(三)
    自动化福音(爬虫、办公、测试等)SeleniumBase使用笔记(三)SeleniumBase制作WEB用户使用导览,并导出JSSeleniumBase包含强大的JS代码生成器,用于将Python转换为JavaScript,而制作用户导览,就是其中的应用之一,用户导览能将SaaS产品采用率提高10倍或更多目录创建导览......
  • 2023 国庆 清北学堂笔记
    2023国庆QBXT未完结,勿喷Day0被GSS6卡了一整天/kkDay1挂大分膜你赛125pts原因是T1100pts->50pts被卡常力啊啊啊啊其实也不是被卡常了我写的\(\mathcal{O(n^3\logn)}\)然而标算\(\mathcal{O(n^3)}\)但有人\(\mathcal{O(n^4)}\)也过去......
  • 2023 暑假 正睿笔记
    Day1"基础"数据结构并查集每次合并集合,就在两个点之间连上边,询问就是看两个点是否在同一连通块但是朴素的并查集复杂度没有保证所以考虑优化路径压缩改变树的结构不会改变它的连通性我们考虑为什么我们之前复杂度会退化很重要一个原因就是有可能路径太长所以我们把......
  • 筛法学习笔记
    埃氏筛枚举质数\(p_i\),每次去除所有是\(p_i\)倍数的数,总效率大概是\(O(n\log\logn)\)。int_prm=0,prm[M];boolisprm[M];voidGet_phi(intn){ for(inti=2;i<=n;i++){ if(isprm[i])continue; prm[++_prm]=i; for(intj=i*i;j<=n;j+=i)isprm[j]=1; }}值......