算法浅谈之树上差分

标签：std   inline   ref   最大   logs   com   cpp   sign   其他   

先放一道例题[USACO15DEC]Max Flow P

题目大意

给你一棵\(n\)个点的树，有\(k\)条管道，每条管道有个起始点和终结点。从起始点到终结点的路径上每个经过的点权值都要\(+1\)

现在问你这\(k\)条管道都处理完后权值最大的点的权值是多少

\(N\le50000\)

\(K\le100000\)

分析

乍一看有一点棘手啊。

如果是条链

我们考虑这棵树是一条链。那么就是一个正常的差分：起始点\(+1\)，终结点后面的点\(-1\)，最后哪一个变量从头加到尾，记录最大值。

其他情况

那就只能用树上差分来做。

树上差分。顾名思义，就是在树上进行差分操作。具体是：起始点和终止点\(+1\)，LCA与LCA的父亲\(-1\)。这样就可以完成树上差分

不会LCA的请看https://www.cnblogs.com/hulean/p/11144059.html

具体为什么的话，画图就很明显了。

dfs

差分处理完后，我们只需要一遍dfs来累加每个点的值，并且维护最大值。

这道题就做完了

#include 
using namespace std ;
const int MAXN = 50000 + 5 ;
struct Node {
	int next , to ;
} edge[ MAXN  ‘9‘ ) { if ( c == ‘-‘ ) f = -1 ; c = getchar () ; }
	while ( c >= ‘0‘ && c = 0 ; i -- ) {
		if ( deep[ fa[ x ][ i ] ] >= deep[ y ] ) x = fa[ x ][ i ] ;
	}
	if ( x == y ) return x ;
	for ( int i = 20 ; i >= 0 ; i -- ) {
		if ( fa[ x ][ i ] != fa[ y ][ i ] ) x = fa[ x ][ i ] , y = fa[ y ][ i ] ;
	}
	return fa[ x ][ 0 ] ;
}
inline void work ( int u , int father ) {
	for ( int i = head[ u ] ; i ; i = edge[ i ].next ) {
		int v = edge[ i ].to ;
		if ( v == father ) continue ;
		work ( v , u ) ;
		w[ u ] += w[ v ] ;
	}
	ans = max ( ans , w[ u ] ) ;
}
signed main () {
	n = read () ; k = read () ;
	for ( int i = 1 ; i 

算法浅谈之树上差分

标签：std   inline   ref   最大   logs   com   cpp   sign   其他   

原文地址：https://www.cnblogs.com/hulean/p/13360407.html