首页 > 其他分享 >【树上点差分、LCA】Max Flow P

【树上点差分、LCA】Max Flow P

时间:2024-08-13 12:54:43浏览次数:16  
标签:hson sz int Max sum Flow ++ LCA top

核心思路

[USACO15DEC] Max Flow P - 洛谷

sum[u]++,sum[v]++,sum[lca(u,v)]--,sum[fa[lca(u,v)]];

本质上就是,对树进行差分

自底向上进行统计处理

#include<bits/stdc++.h>
using namespace std;
int  n,m;
const int N = 200000+10;
vector<int> G[N] ;
int dep[N],fa[N],hson[N],sz[N],top[N],dfn[N],res[N];
//____________________________________分割线。 
void dfs1(int u,int p){//u当前访问到的,p父节点。
	fa[u] = p;
	sz[u] = 1;
	dep[u] = dep[p]+1;
	hson[u] = -1;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(v == p)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(hson[u] == -1|| sz[v] > sz[hson[u]]){
			hson[u] = v;
		}
	} 
 
	
}
int cnt;//记录是第几次访问 
void dfs2(int u,int p){
    if(u == 1)top[1] = 1;
    //先遍历重儿子 
    cnt++;
	dfn[u] = cnt; 
	res[cnt] = u;
	if(hson[u] == -1)return;
	top[hson[u]] = top[u];
    dfs2(hson[u],u); 
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(v == p || hson[u] == v)continue;
		top[v] = v;
	    dfs2(v,u);
	} 
}
int lca(int u,int v){
	if(top[u] == top[v])return dep[u]<dep[v] ? u : v;//那个深度小就取哪个。
	if(dep[top[u]]<dep[top[v]]) return lca(u,fa[top[v]]);
	else return lca(fa[top[u]],v);
	//因为他是要跳到top的父亲上所以要比较两个top的深度; 
}
int sum[114514];
int ans = 0;
void ges(int u,int f){
	for(int v:G[u]){
		if(v == f)continue;
		ges(v,u);
		sum[u]+=sum[v];
	}ans = max(sum[u],ans);
}
int main(){
	cin>>n>>m;
	for(int i = 1;i <= n-1;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);G[v].push_back(u);
	} 
	dfs1(1,0);dfs2(1,0);
	while(m--){
		int u,v;
		cin>>u>>v;
		int L = lca(u,v);
		sum[u]++,sum[v]++;
		sum[L]--,sum[fa[L]]--;
	}
	ges(1,0);cout<<ans<<endl;
	return 0;
}

 

标签:hson,sz,int,Max,sum,Flow,++,LCA,top
From: https://blog.csdn.net/2301_77025310/article/details/141154778

相关文章

  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance
    https://codeforces.com/contest/1881/problem/F不难发现一件事情,我们这里最后的答案所在的点是1和3号点。我们有没有发现一个性质:就是这两个点都是红点间的路径上的,而且最后的答案就是最长的红点间的距离的长度除以二上取整。那么,我们怎么找到最长的红点间的距离呢?很显......
  • 计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析
    基于Tensorflow的股票推荐与预测系统的设计与实现开题报告一、研究背景与意义在信息技术高速发展的今天,金融市场日益复杂,投资者面临着越来越多的选择和挑战。股票作为金融市场的重要组成部分,其价格波动受到多种因素的影响,包括宏观经济、政策变化、公司业绩等。因此,如何准确......
  • TensorFlow简介,应用场景,使用方法以及项目实践及案例分析,附带源代码
    一、TensorFlow简介TensorFlow是由GoogleBrain团队开发的开源机器学习库,广泛用于各种复杂的数学计算,特别是涉及深度学习的计算。它提供了丰富的工具和资源,用于构建和训练机器学习模型。TensorFlow的核心是计算图(ComputationGraph),这是一种用于表示计算流程的图结构,由节点(代表......
  • Nginx负载均衡的max_fails和fail_timeout的默认配置问题
    今天发现一个奇怪的现象,前端请求后端服务多次后会超时一次,经过多次验证确定是大概10s左右就会超时一次,检查后端服务,发现其中一个节点已经夯死。但是我们的nginx负载均衡策略是轮询机制,按照配置来看应该是每隔一次请求轮询到失败的节点时超时一次才对。为什么是每隔10s超时一次呢?......
  • ABC366F Maximum Composition 题解
    ABC366FMaximumComposition题解题目大意给定\(N\)个一次函数\(f_i(x)=a_ix+b_i\),从中选出\(K\)个函数\(f_{p_1},f_{p_2},\dots,f_{p_K}\),使得\(f_{p_1}(f_{p_2}(\dotsf_{p_K}))\)最大,求最大值。Solve考虑这样一种情况:我已经选定\(p_{k+1},p_{k+1},\dots,p_K\),现......
  • glm_oneflow基于Oneflow框架的glm-10b-chinese自然语言处理
    GLM论文GLM:GeneralLanguageModelPretrainingwithAutoregressiveBlankInfillinghttps://arxiv.org/abs/2103.10360模型结构2017年,Google提出了Transformer架构,随后BERT、GPT、T5等预训练模型不断涌现,并在各项任务中都不断刷新SOTA纪录。2022年,清......
  • 工作流之Flowable与SpringBoot结合
    目录1Flowable1.1flowable-ui部署运行1.2绘制流程图1.2.1绘制1.2.2绘图细节1.2.3bpmn文件导入1.3后台项目搭建1.3.1pom.xml1.3.2数据库表说明1.4流程引擎API与服务1.4.1主要API1.4.2示例1Flowable1.1flowable-ui部署运行flowable-6.6.0运行官方demo参考文档:ht......
  • 【大作业-17】使用TensorFlow快速实现图像风格迁移系统
    使用TensorFlow快速实现图像风格迁移系统资源地址:28-基于Tensorflow的风格迁移+代码+模型+系统界面+教学视频.zip资源-CSDN文库视频地址:[使用Tensorflow实现图像风格迁移系统_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1VE421w7RY/)随着GPT的横空出世,生成......
  • Flow -- 理解(面试官最爱问的7个Flow问题)
    1、问题: 请解释Flow是什么,与传统的RxJava相比有何优势?出发点:在回答这个问题时,应当强调对Flow的理解以及与RxJava的对比。涉及到Flow的背后原理、冷流、热流的概念,以及在响应式编程中的应用场景。参考简答:Flow是一种基于协程的响应式编程库,用于处理异步数据流。与RxJava相......
  • 数值稳定性:Fixing NaN Gradients during Backpropagation in TensorFlow
    数值稳定性:FixingNaNGradientsduringBackpropagationinTensorFlow......