「USACO2015」最大流 - 树上差分_usaco 差分-程序员宅基地

题目大意

给定一棵有N个点的树，所有节点的权值都为0。有K次操作，每次指定两个点s,t，将s到t路径上所有点的权值都加一，最后输出K次操作完毕后权值最大的那个点的权值。

分析

算得上是树上差分的模板题了。

说一下普通的差分。现在有这么一个问题，给定一个序列A，有K个修改，每个修改将[L,R]中的数加1，最后问其中的最大数。最普通的做法就是每次跑一遍[L,R]，并更新最大值，显然这样做可能会TLE；而差分的做法就将区间修改转化为点修改。定义差分序列D， $D[i]=A[i]-A[i-1]$ ，易知D的前缀和就是原数组。而如果在 $D[L]$ 处+1，则对于所有的 $i\geq L,D[i]$ 都会+1，在 $D[R+1]$ 处-1，则对于所有的 $i > R,D[i]$ 都会-1，重叠部分与+1抵消，故改变的只有[L,R]。修改结束后，统计一遍前缀和，找最大数即可解决。

同理在树上的差分也是如此。若想让图中u到v上的每条边的权值+1，可以让 $w[u]++,w[v]++,w[LCA(u,v)]-=2$ ，其中 $w[i]$ 表示 $i$ 号节点与它父亲之间的边，最后通过一次DFS，统计前缀和，即 $w[i]+=w[j]$ （i是j的父亲）。

对于点权的差分，大体是差不多的，减的时候让 $w[LCA(u,v)]--,w[father[LCA(u,v)]]--$ ，因为对于点， $LCA(u,v)$ 在这条链上，而它只能加一个，所以++，它++，它的父亲也会++，所以它的父亲要--。

Tree

本题根据题意是点的差分，所以按照第二种方法即可。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
struct node {
	int to,next;
}e[50005*2];
int h[50005],cnt,dth;
int n,k,dep[50005],ans;
int f[50005][20],v[50005];
void add(int x,int y) {
	e[++cnt]=(node){y,h[x]};
	h[x]=cnt;
}
void FindDepth(int x,int prt) {
	dep[x]=dep[prt]+1;
	for (int i=h[x];i;i=e[i].next) {
		int y=e[i].to;
		if (y==prt) continue;
		f[y][0]=x;
		FindDepth(y,x);
	}
}
int GetLca(int x,int y) {
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=dth;i>=0;i--)
		if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (int i=dth;i>=0;i--)
		if (f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
void Dfs(int x,int prt) {
	for (int i=h[x];i;i=e[i].next) {
		int y=e[i].to;
		if (y==prt) continue;
		Dfs(y,x);
		v[x]+=v[y];
	}
	ans=max(ans,v[x]);
}
int main() {
	scanf("%d%d",&n,&k);
	for (int i=1,a,b;i<n;i++) {
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dth=(int)(log(n)/log(2));
	FindDepth(1,0);
	for (int j=1;(1<<j)<=n;j++)
		for (int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	
	for (int i=1,a,b;i<=k;i++) {
		scanf("%d%d",&a,&b);
		v[a]++;
		v[b]++;
		int t=GetLca(a,b);
		v[t]--;
		v[f[t][0]]--;
	}
	Dfs(1,0);
	printf("%d",ans);
	return 0;
}

本文链接：https://blog.csdn.net/sin_Yang/article/details/82226042

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

前端开发之vue-grid-layout的使用和实例-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout

Power Apps-上传附件控件_powerapps点击按钮上传附件-程序员宅基地

文章浏览阅读218次。然后连接一个数据源，就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里，就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件

C++ 面向对象（Object-Oriented）的特征 & 构造函数& 析构函数_"object(cnofd[\"ofdrender\"])十条"-程序员宅基地

文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"

修改node_modules源码，并保存，使用patch-package打补丁，git提交代码后，所有人可以用到修改后的_修改 node_modules-程序员宅基地

文章浏览阅读133次。删除node_modules，重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules

【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure-程序员宅基地

文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure

整理5个优秀的微信小程序开源项目_微信小程序开源模板-程序员宅基地

文章浏览阅读1w次，点赞13次，收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板

随便推点

Centos7最简搭建NFS服务器_centos7 搭建nfs server-程序员宅基地

文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server

Springboot整合Mybatis-Plus使用总结(mybatis 坑补充)_mybaitis-plus ruledataobjectattributemapper' and '-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏3次。前言mybatis在持久层框架中还是比较火的，一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库，很是灵活。但正其操作都要通过SQL语句进行，就必须写大量的xml文件，很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d

EECE 1080C / Programming for ECESummer 2022 Laboratory 4: Global Functions Practice_eece1080c-程序员宅基地

文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c

洛谷p4777 【模板】扩展中国剩余定理-程序员宅基地

文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学，wtcl。设要求的数为$x$。设当前处理到第$k$个同余式，设$M = LCM ^ {k - 1} _ {i - 1}$ ，前$k - 1$个的通解就是$x + i * M$。那么其实第$k$个来说，其实就是求一个$y$使得$x + y * M ≡ a_k(mod b_k)$转化一下就是\(y * M ...

android 退出应用没有走ondestory方法,[Android基础论]为何Activity退出之后，系统没有调用onDestroy方法？...-程序员宅基地

文章浏览阅读1.3k次。首先，问题是如何出现的？晚上复查代码，发现一个activity没有调用自己的ondestroy方法我表示非常的费解，于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy

SylixOS快问快答_select函数导致堆栈溢出 sylixos-程序员宅基地

文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数导致堆栈溢出 sylixos