动态DP教程

前言
开始
更进一步

前言

~~最后一届NOIP~~TG的day2T3对于动态DP的普及起到了巨大的作用。~~然而我到现在还不会~~

开始

SP1716 GSS3 - Can you answer these queries III

题解位置

这道题的题目大意就是维护动态序列最大子段和。一个比较显然的想法就是用线段树维护(lmax,rmax,sum,max)即可。但是我们不想放弃DP的优良性质，于是就有了优良的动态DP。

对于这道题目，如果不考虑修改操作，那么DP就是这样的：

令(F[i])表示以(A[i])为结尾的最大子段和，(G[i])表示到(i)为止的答案，那么不难发现

[F[i]=A[i]+max{F[i-1],0}\ G[i]=max{G[i-1],F[i]} ]

下一步就是把转移改写为矩乘的形式。能够改写是因为矩乘基于乘法对加法的分配律。而max同样对加法有分配律。也就是说：

[a(b+c)=ab+ac\ a+max{b,c}=max{a+b,a+c} ]

这样，上面的Dp就可以变成这个样子：

[F[i]=max{A[i]+F[i-1],A[i]}\ G[i]=max{G[i-1],F[i-1]+A[i],A[i]} ]

那么转移矩阵就应该是一个(3 imes3)的矩阵。

[egin{aligned} left [egin{matrix} A[i]&-infty&A[i]\ A[i]&0&A[i]\ -infty & -infty & 0 end{matrix} ight] left [egin{matrix} F[i-1]\ G[i-1]\ 0 end{matrix} ight] = left [egin{matrix} F[i]\ G[i]\ 0 end{matrix} ight] end{aligned} ]

只是这个矩阵乘法是

[C_{i,j}=max{A_{i,k}+B_{k,j}} ]

那么根据矩阵乘法的结合律，用线段树维护即可。

更进一步

真正展示动态DP厉害的地方在树上。

【模板】动态 DP

首先明确最大权独立集的含义：选择若干的点，他们互不相邻，使得点权和最大。

对付这道题目，我们同样先把最朴素的Dp写出来（(F[u][0])代表不选当前点，(F[u][1])代表选当前点）：

void Dp( int u, int Fa ) {
	F[ u ][ 1 ] = A[ u ];
	for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {
		int v = Edge[ t ].To;
		if( v == Fa ) continue;
		Dp( v, u );
		F[ u ][ 1 ] += F[ v ][ 0 ];
		F[ u ][ 0 ] += max( F[ v ][ 0 ], F[ v ][ 1 ] );
	}
	return;
}

好像不知道怎么改成矩乘是吧。

不妨先看一看一条链的情况。

[F[i][0]=max{F[i-1][0],F[i-1][1]}\ F[i][1]=A[i]+F[i-1][0]\ ]

然后改写成矩乘

[egin{aligned} left[egin{matrix} 0 & 0\ A[i]&-infty end{matrix} ight] left[egin{matrix} F[i-1][0]\ F[i-1][1] end{matrix} ight] = left[egin{matrix} F[i][0]\ F[i][1] end{matrix} ight] end{aligned} ]

既然可以在链上做，那么就可以考虑一下树剖。

现在剩余的问题在于轻儿子的转移。

不妨令(G[i][0])表示不选(i)时去掉(i)的重儿子的答案，相对应的(G[i][1])表示选(i)时去掉(i)的重儿子的答案。

如果用(Son[ i ])表示(i)的重儿子，那么不难发现

[egin{aligned} left[egin{matrix} G[i][0] & G[i][0]\ G[i][1] &-infty end{matrix} ight] left[egin{matrix} F[Son[i]][0]\ F[Son[i]][1] end{matrix} ight] = left[egin{matrix} F[i][0]\ F[i][1] end{matrix} ight] end{aligned} ]

那么点(u)的(F[u])可以通过这个点到这条链的底部的矩阵乘积之和。（这里的矩阵指的就是上面那个含有(G)的矩阵。）注意这里的矩阵是左乘，所以顺序应该是从深度小的一端乘到深度大的一端。

最后一步，维护(G)的值。其实修改也很简单。考虑到最原始的Dp，如果修改了轻儿子(v)的值，那么只要

G[i][0] += -max( Last[v][0], Last[v][1] ) + max( New[v][0], New[v][1] );
G[i][1] += -Last[v][0] + New[v][0];

然后在线段树上更新一下就好了。就是用新的值直接修改就好。这样所有的地方都走通了。

~~为了降低代码可读性，所以没有删去调试信息，看起来爽【滑稽】~~

#include <bits/stdc++.h>
#include <unistd.h>
//#define Debug
using namespace std;

const int Maxn = 100010;
const int INF = 1000000000;
struct matrix {
	int A[ 2 ][ 2 ];
	matrix() {
		A[ 0 ][ 0 ] = A[ 0 ][ 1 ] = A[ 1 ][ 0 ] = A[ 1 ][ 1 ] = -INF;
		return;
	}
	matrix( int x, int y ) {
		A[ 0 ][ 0 ] = A[ 0 ][ 1 ] = x;
		A[ 1 ][ 0 ] = y;
		A[ 1 ][ 1 ] = -INF;
		return;
	}
	matrix( int a, int b, int c, int d ) {
		A[ 0 ][ 0 ] = a; A[ 0 ][ 1 ] = b; A[ 1 ][ 0 ] = c; A[ 1 ][ 1 ] = d;
		return;
	}
	inline matrix operator * ( const matrix Other ) const {
		matrix Ans = matrix();
		for( int i = 0; i < 2; ++i )
			for( int j = 0; j < 2; ++j )
				for( int k = 0; k < 2; ++k )
					Ans.A[ i ][ j ] = max( Ans.A[ i ][ j ], A[ i ][ k ] + Other.A[ k ][ j ] );
#ifdef Debug
		printf( "%15d %15d    %15d %15d    %15d %15d
", A[ 0 ][ 0 ], A[ 0 ][ 1 ], Other.A[ 0 ][ 0 ], Other.A[ 0 ][ 1 ], Ans.A[ 0 ][ 0 ], Ans.A[ 0 ][ 1 ] );
		printf( "%15d %15d    %15d %15d    %15d %15d
", A[ 1 ][ 0 ], A[ 1 ][ 1 ], Other.A[ 1 ][ 0 ], Other.A[ 1 ][ 1 ], Ans.A[ 1 ][ 0 ], Ans.A[ 1 ][ 1 ] );
#endif
		return Ans;
	}
};
struct edge {
	int To, Next;
	edge() {}
	edge( int _To, int _Next ) : To( _To ), Next( _Next ) {}
};
edge Edge[ Maxn << 1 ];
int Start[ Maxn ], UsedEdge;
int n, m, A[ Maxn ];
int Deep[ Maxn ], Father[ Maxn ], Size[ Maxn ], Son[ Maxn ], Top[ Maxn ], Dfn[ Maxn ], Ind[ Maxn ], Ref[ Maxn ], Used; 
int Dp[ Maxn ][ 2 ], LDp[ Maxn ][ 2 ];
matrix G[ Maxn ], Tree[ Maxn << 2 ];

inline void AddEdge( int x, int y ) { Edge[ ++UsedEdge ] = edge( y, Start[ x ] ); Start[ x ] = UsedEdge; return; }

void Dfs1( int u, int Fa ) {
	Deep[ u ] = Deep[ Fa ] + 1; Father[ u ] = Fa; Size[ u ] = 1;
	for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {
		int v = Edge[ t ].To;
		if( v == Fa ) continue;
		Dfs1( v, u );
		Size[ u ] += Size[ v ];
		if( Size[ v ] > Size[ Son[ u ] ] ) Son[ u ] = v;
	}
}

void Dfs2( int u, int Fa ) {
	if( Son[ u ] ) {
		Top[ Son[ u ] ] = Top[ u ]; Ind[ Son[ u ] ] = ++Used; Ref[ Used ] = Son[ u ];
		Dfs2( Son[ u ], u );
	}
	for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {
		int v = Edge[ t ].To;
		if( v == Fa || v == Son[ u ] ) continue;
		Top[ v ] = v; Ind[ v ] = ++Used; Ref[ Used ] = v;
		Dfs2( v, u );
	}
	return;
}

void Build( int u, int Fa ) {
	LDp[ u ][ 1 ] = A[ u ];
	for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {
		int v = Edge[ t ].To;
		if( v == Fa || v == Son[ u ] ) continue;
		Build( v, u );
		LDp[ u ][ 0 ] += max( Dp[ v ][ 0 ], Dp[ v ][ 1 ] );
		LDp[ u ][ 1 ] += Dp[ v ][ 0 ];
	}
	if( Son[ u ] ) Build( Son[ u ], u );
	Dp[ u ][ 0 ] = LDp[ u ][ 0 ] + max( Dp[ Son[ u ] ][ 0 ], Dp[ Son[ u ] ][ 1 ] );
	Dp[ u ][ 1 ] = LDp[ u ][ 1 ] + Dp[ Son[ u ] ][ 0 ];
	G[ u ] = matrix( LDp[ u ][ 0 ], LDp[ u ][ 1 ] );
	if( Son[ u ] ) G[ u ] = G[ u ] * G[ Son[ u ] ];
	return;
}

void BuildTree( int Index, int Left, int Right ) {
	if( Left == Right ) {
		Tree[ Index ] = matrix( LDp[ Ref[ Left ] ][ 0 ], LDp[ Ref[ Left ] ][ 1 ] );
		return;
	}
	int Mid = ( Left + Right ) >> 1;
	if( Left <= Mid ) BuildTree( Index << 1, Left, Mid );
	if( Right > Mid ) BuildTree( Index << 1 | 1, Mid + 1, Right );
#ifdef Debug
	printf( " %d %d <-- %d %d  +  %d %d
", Left, Right, Left, Mid, Mid + 1, Right );
#endif
	Tree[ Index ] = Tree[ Index << 1 ] * Tree[ Index << 1 | 1 ];
	return;
}

matrix Query( int Index, int Left, int Right, int L, int R ) {
	if( L <= Left && Right <= R ) return Tree[ Index ];
	int Mid = ( Left + Right ) >> 1;
	if( R <= Mid ) return Query( Index << 1, Left, Mid, L, R );
	if( L > Mid ) return Query( Index << 1 | 1, Mid + 1, Right, L, R );
	return Query( Index << 1, Left, Mid, L, R ) * Query( Index << 1 | 1, Mid + 1, Right, L, R );
}

void Update( int Index, int Left, int Right, int Pos ) {
	if( Left == Right ) {
		Tree[ Index ] = matrix( LDp[ Ref[ Left ] ][ 0 ], LDp[ Ref[ Left ] ][ 1 ] );
		return;
	}
	int Mid = ( Left + Right ) >> 1;
	if( Pos <= Mid ) Update( Index << 1, Left, Mid, Pos );
	if( Pos > Mid ) Update( Index << 1 | 1, Mid + 1, Right, Pos );
	Tree[ Index ] = Tree[ Index << 1 ] * Tree[ Index << 1 | 1 ];
	return;
}

void Change( int u, int Key ) {
	LDp[ u ][ 1 ] += -A[ u ] + Key; A[ u ] = Key;
	matrix Last = G[ Top[ u ] ];
	Update( 1, 1, n, Ind[ u ] );
	G[ Top[ u ] ] = Query( 1, 1, n, Ind[ Top[ u ] ], Dfn[ Top[ u ] ] );
#ifdef Debug
	printf( " u = %d, %d %d
", u, LDp[ u ][ 0 ], LDp[ u ][ 1 ] );
	printf( " Tu = %d, %d %d
", Top[ u ], G[ Top[ u ] ].A[ 0 ][ 0 ], G[ Top[ u ] ].A[ 1 ][ 0 ] );
#endif
	int Son = Top[ u ];
	u = Father[ Top[ u ] ];
	while( u ) {
		LDp[ u ][ 0 ] += -max( Last.A[ 0 ][ 0 ], Last.A[ 1 ][ 0 ] ) + max( G[ Son ].A[ 0 ][ 0 ], G[ Son ].A[ 1 ][ 0 ] );
		LDp[ u ][ 1 ] += -Last.A[ 0 ][ 0 ] + G[ Son ].A[ 0 ][ 0 ];
		Last = G[ Top[ u ] ];
#ifdef Debug
		printf( "Update %d
", u );
#endif
		Update( 1, 1, n, Ind[ u ] );
#ifdef Debug
		printf( "Query %d %d
", Ind[ Top[ u ] ], Dfn[ Top[ u ] ] );
#endif
		G[ Top[ u ] ] = Query( 1, 1, n, Ind[ Top[ u ] ], Dfn[ Top[ u ] ] );
#ifdef Debug
		printf( " u = %d, %d %d
", u, LDp[ u ][ 0 ], LDp[ u ][ 1 ] );
		printf( " Tu = %d, %d %d
", u, G[ Top[ u ] ].A[ 0 ][ 0 ], G[ Top[ u ] ].A[ 1 ][ 0 ] );
#endif
		Son = Top[ u ];
		u = Father[ Top[ u ] ];
	}
	return;
}

int main() {
	scanf( "%d%d", &n, &m );
	for( int i = 1; i <= n; ++i ) scanf( "%d", &A[ i ] );
	for( int i = 1; i < n; ++i ) {
		int x, y; scanf( "%d%d", &x, &y );
		AddEdge( x, y ); AddEdge( y, x );
	}
	Dfs1( 1, 0 );
	Top[ 1 ] = 1; Ind[ 1 ] = ++Used; Ref[ Used ] = 1;
	Dfs2( 1, 0 );
	for( int i = 1; i <= n; ++i ) Dfn[ Top[ i ] ] = max( Dfn[ Top[ i ] ], Ind[ i ] );
	Build( 1, 0 );
	BuildTree( 1, 1, n );
#ifdef Debug
	printf( "Used : %d
", Used );
	printf( "Top  : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Top[ i ] ); printf( "
" );
	printf( "Son  : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Son[ i ] ); printf( "
" );
	printf( "Ind  : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Ind[ i ] ); printf( "
" );
	printf( "Ref  : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Ref[ i ] ); printf( "
" );
	printf( "Dfn  : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Dfn[ i ] ); printf( "
" );
	printf( "Fa   : " ); for( int i = 1; i <= n; ++i ) printf( "%d ", Father[ i ] ); printf( "
" );
	printf( "%d ", max( Dp[ 1 ][ 0 ], Dp[ 1 ][ 1 ] ) );
	printf( "%d
", max( G[ 1 ].A[ 0 ][ 0 ], G[ 1 ].A[ 1 ][ 0 ] ) );
	for( int i = 1; i <= n; ++i ) printf( "  ( %d, %d, %d, %d )
", LDp[ i ][ 0 ], LDp[ i ][ 1 ], Dp[ i ][ 0 ], Dp[ i ][ 1 ] );
	printf( "Testing...
" );
	int IsOk = 1;
	for( int i = 1; i <= n; ++i ) {
		printf( " %d : Check %d To %d
", i, Ind[ i ], Dfn[ Top[ i ] ] );
		matrix Temp = Query( 1, 1, n, Ind[ i ], Dfn[ Top[ i ] ] );
		printf( " ---> %d - %d %d - %d
", Temp.A[ 0 ][ 0 ], Dp[ i ][ 0 ], Temp.A[ 1 ][ 0 ], Dp[ i ][ 1 ] );
		if( Temp.A[ 0 ][ 0 ] != Dp[ i ][ 0 ] || Temp.A[ 1 ][ 0 ] != Dp[ i ][ 1 ] ) printf( "Err %d
", i ), IsOk = 0;
	}
	if( IsOk ) printf( "Ok.
" ); else {
		printf( "Ooooops.
" );
		return 0;
	}
	for( int i = 1; i <= n; ++i ) {
		printf( " %d : %d - %d,    %d - %d
", i, Dp[ i ][ 0 ], G[ i ].A[ 0 ][ 0 ], Dp[ i ][ 1 ], G[ i ].A[ 1 ][ 0 ] );
		if( Dp[ i ][ 0 ] != G[ i ].A[ 0 ][ 0 ] || Dp[ i ][ 1 ] != G[ i ].A[ 1 ][ 0 ] ) {
			printf( "Err
" );
			IsOk = 0;
		}
	}
	if( IsOk ) printf( "Ok.
" ); else {
		printf( "Ooooops.
" );
		return 0;
	}
#endif
	for( int i = 1; i <= m; ++i ) {
		int x, y; scanf( "%d%d", &x, &y );
		Change( x, y );
		printf( "%d
", max( G[ 1 ].A[ 0 ][ 0 ], G[ 1 ].A[ 1 ][ 0 ] ) );
#ifdef Debug
		sleep( 1 );
#endif
	}
	return 0;
}