【图论】树上差分(点差分)

这篇具有很好参考价值的文章主要介绍了【图论】树上差分(点差分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.题目

P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


二 .分析

我们可以先建一棵树

【图论】树上差分(点差分),图论,图论,算法

但我们发现,这样会超时。

所以,我们想到树上差分

【图论】树上差分(点差分),图论,图论,算法文章来源地址https://www.toymoban.com/news/detail-628505.html

三.代码

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5 
3 4
*/

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m;
int head[maxn],depth[maxn],p[maxn][25],d[maxn];
struct Edge{
	int u,v,next;
}edge[maxn<<1];
int cnt=0;
void add(int u,int v){
	edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
void dfs(int u,int fa){
	depth[u]=depth[fa]+1;
	p[u][0]=fa;
	for(int i=1;(1<<i)<=depth[u];i++){
		p[u][i]=p[p[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v!=fa){
			dfs(v,u);
		}
	}
}
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	int lg=0;
	while((1<<lg)<=depth[x]) lg++;
	for(int i=lg;i>=0;i--){
		if(depth[x]-(1<<i)>=depth[y]) x=p[x][i];
	}
	if(x==y) return x;
	for(int i=lg;i>=0;i--){
		if(p[x][i]!=p[y][i]){
			x=p[x][i]; y=p[y][i];
		}
	}
	return p[x][0];
}
void dfs2(int u,int fa){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v!=fa){
			dfs2(v,u);
			d[u]+=d[v];
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;add(u,v);add(v,u);
	}
	dfs(1,0); //建树 
	while(m--){
		int u,v; cin>>u>>v;
		d[u]++; d[v]++;
		int lc=lca(u,v);
		d[lc]--; d[p[lc][0]]--;
	}
	dfs2(1,0); //sum求原数组 
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,d[i]);
	}
	cout<<ans;
	return 0;
}

到了这里,关于【图论】树上差分(点差分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

    树上倍增 内向基环树 图论 给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。 总共有 n 名玩家,玩家 编号 互不相同,且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏,receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己,

    2024年04月17日
    浏览(41)
  • 【图论】差分约束

    x1-x0=9 ; x2-x0=14 ; x3-x0=15 ; x2-x1=10 ; x3-x2=9; 求x3-x0的最大值; 联立式子2和5,可得x3-x0=23;但式子3可得x3-x0=15。所以最大值为15; 但式子多了我们就不好解了,或者说在计算机中怎么解呢? 我们可以想到,不妨把式子转为图的形式。我们令x0--x1的边表示为x1-x0=边权值。 则以上式子

    2024年02月13日
    浏览(37)
  • 【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目

    【动态规划】【数学】【C++算法】18赛车 差分数组 图论 分类讨论 整除以2 给你三个 正整数 n 、x 和 y 。 在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1 = i n ,都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与

    2024年01月22日
    浏览(37)
  • 【算法】树形DP ② 打家劫舍Ⅲ(树上最大独立集)

    最大独立集 需要从图中选择尽量多的点,使得这些点互不相邻。 337. 打家劫舍 III 用一个数组 int[] = {a, b} 来接收每个节点返回的结果 。返回值{a,b} a表示没选当前节点的最大值,b表示选了当前节点的最大值。 使用 后序遍历 dfs。 ( 发现树形 DP 基本都是后序 dfs ) P1352 没有上

    2024年02月12日
    浏览(45)
  • 二维差分算法详解

    二维差分模板 给定一个n行m列的矩阵,下标从1开始。接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k,表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。请输出操作后的矩阵。 第一行包含三个整数n,m,q。接下来n行,每行m个整数,代表矩阵的元素。接

    2024年01月20日
    浏览(45)
  • 蓝桥杯一维差分 | 算法基础

    ⭐ 简单说两句 ⭐ ✨ 正在努力的小新~ 💖 超级爱分享,分享各种有趣干货! 👩‍💻 提供:模拟面试 | 简历诊断 | 独家简历模板 🌈 感谢关注,关注了你就是我的超级粉丝啦! 🔒 以下内容仅对你可见~ 作者: 后端小知识 , CSDN后端领域新星创作者 |阿里云专家博主 CSDN 个

    2024年02月03日
    浏览(43)
  • 差分算法及模板详解

    ⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法

    2023年04月09日
    浏览(53)
  • 算法专题:差分数组

    2024年01月18日
    浏览(33)
  • 算法之路-------差分数组

    针对数组中连续的大量数据进行修改的问题,如果我们对每个数据都进行依次修改,对于一些少量的数据的修改(例如:1~100这些的),修改的时候我们发现速度貌似还是很快的,但是一旦修改的连续数组中的数量上万了,那么修改的速率就明显下降了。 所以:针对这样的情

    2024年02月06日
    浏览(50)
  • 差分算法介绍

    一、一维差分基本概念 差分算法是前缀和算法的逆运算,可以快速的对数组的某一区间进行计算操作。 例如,有一数列 a[1],a[2],.…a[n],且令 b[i] = a[i]-a[i-1],b[1]=a[1],那么就有 a[i] = b[1]+b[2]+.…+b[i] = a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1],此时b数组称作a数组的差分数组 ,换句话来说

    2024年01月25日
    浏览(74)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包