【DP】【동적 DP】BZOJ5210 최대련 통자 블록과

분석:

동적 DP 보드 서브 문제, DP 정의식은 f(i, 0), f(i, 1) f(i, 0), f(i, 1) f(i, 0), f(i, 1)는 각각 i를 뿌리로 하는 서브 트리의 최대치, i를 뿌리로 하는 서브 트리의 최대 답안, i를 뿌리로 하는 서브 트리에서 i와 연결된 최대 연결 서브 트리를 나타낸다.
전이: f(x, 1) = max'8889(u, 1) + v x x, 0} f(x, 1) =\max\{\sum f(u, 1) +val x, 0\} f(u, 1) x x, 0} x, 0} x, 0} x, 0} f(x, 1) =\max\max\\\\{{{{{\sum f(u, 1, 1) x x x x x x x x x x x = max {f(u, 1) x (x, 1) = max (x, f(x, 1) (x, 1) (x, 1) (x, 1) (x, 1) (x, 1) (x, x,))))) ((x, x,)) f(x,0)=max{f(u,0)}, f(x,1)} 중 u는 x의 하위 노드입니다.
그 다음에 경아들 lf(x, 1) = max ⁡ {∑f(l u, 1) + v a l x, 0} lf(x, 1) =\max\\max {\sum f(lu, 1) +val x, 0\} lf (x, 1) = max {∑f (lu, 1) + valx, l f (x, 0) = l f (x, 0) = max {{{f(l u, u, 0) (l, 0)} (l, l, l), l) (l, l)) (l,)), 1), (l)), 1), x {x {x {x {x {x {, {x {x {, {f, lf(x,1)\}lf(x,0)=max{f(lu,0)},lf(x,1)} 두 번째 max를 찾으려면 set가 유지해야 합니다
그 다음은 중체인 f(i, 1) = ∑f(i 1, 1) + l f(i, 1) f(i, 1) f(i, 1) =\sum f(i-1, 1) + lf(i, 1) f(i, 1) = ∑f(i, 1, 1) +lf(i, 1) f(i, 1) f(i, 0) = max (8, 0) = max 8289(i-1, 1, 0), lf(i, 0) (i, 0) f(i, 0) f(i, 0) f(i, 0) (i, i, 0) (i, 0) = = =\i-) =\i, {i, {f, {f) {f, {f, {f, f(lf, f, f, f)) {f, f(lf, f, f, f, f, f, f, f, f, i-3, 1,0),lf(i,0)}
쉽게 전이 행렬을 얻을 수 있다. [0, f(i, 0), f(i, 1)] [0l f(i, 0) 00의 0-∞ 00-∞ 0, f(i, 0), f(i, 1)] [0l f(i, 1)] [0l f(i, 1), f(i, 1)] * *\begiin {bmatrix} 0 & 0 & lf (i, 0) & 0 & 0 f(i, 1), f(i, 1), f(i, 1)] * * *\begiin {bmatrix} 0 & 0 & 0 & lf(i, 0) 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\& 0\-∞ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i,1) [0-∞-∞lf(i,0)0lf(i,1) 0-∞lf(i,1)

#include
#include
#include
#include
#include
#define SF scanf
#define PF printf
#define MAXN 200010
#define INF 10000000000000000ll
using namespace std;
typedef long long ll;
struct Matrix{
	ll a[3][3];
	Matrix operator *(const Matrix &b) const {
		Matrix tmp;
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				tmp.a[i][j]=-INF;
		for(int k=0;k<3;k++)
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					tmp.a[i][j]=max(tmp.a[i][j],a[i][k]+b.a[k][j]);
		return tmp;
	}
	ll* operator [](const int &x){
		return a[x];
	}
}mul[MAXN],w[MAXN];
multiset<ll> maxp[MAXN];
ll val[MAXN];
int siz[MAXN],son[MAXN],lsiz[MAXN];
int s[MAXN][2];
struct node{
	int u;
	node *nxt;	
}edge[MAXN*2];
node *head[MAXN],*ncnt=edge;
void add_edge(int u,int v){
	ncnt++;
	ncnt->u=v;
	ncnt->nxt=head[u];
	head[u]=ncnt;
	
	ncnt++;
	ncnt->u=u;
	ncnt->nxt=head[v];
	head[v]=ncnt;	
}
void dfs(int x){
	siz[x]=1;
	for(node *e=head[x];e;e=e->nxt){
		int u=e->u;
		if(siz[u])
			continue;
		dfs(u);
		siz[x]+=siz[u];
		if(siz[u]>siz[son[x]])
			son[x]=u;
	}
}
void update(int x){
	if(s[x][0]||son[x]==0)
		mul[x]=mul[s[x][0]]*w[x];
	else
		mul[x]=w[x];
	if(s[x][1])
		mul[x]=mul[x]*mul[s[x][1]];
}
int fa[MAXN];
void setchild(int u,int v){
	w[u][2][1]+=mul[v][0][2];
	w[u][2][2]=w[u][2][1];
	maxp[u].insert(mul[v][0][1]);
	w[u][0][1]=*maxp[u].rbegin();
	w[u][0][1]=max(w[u][0][1],w[u][2][1]);
	fa[v]=u;	
}
bool used[MAXN];
int st[MAXN],tp;
int build(int l,int r){
	if(l>r)
		return 0;
	int tots=0,pres=0;
	for(int i=l;i<=r;i++)
		tots+=lsiz[i];
	for(int i=l;i<=r;i++){
		pres+=lsiz[i];
		if(pres*2>=tots){
			int x=st[i];
			s[x][0]=build(l,i-1);
			s[x][1]=build(i+1,r);
			if(s[x][0])
				fa[s[x][0]]=x;
			if(s[x][1])
				fa[s[x][1]]=x;
			update(x);
			return x;
		}
	}
}
int build_tree(int x){
	for(int i=x;i;i=son[i]){
		used[i]=1;
		lsiz[i]=siz[i]-siz[son[i]];
	}
	for(int i=x;i;i=son[i])
		for(node *e=head[i];e;e=e->nxt){
			int u=e->u;
			if(used[u])
				continue;
			int rs=build_tree(u);	
			setchild(i,rs);
		}
	tp=0;
	for(int i=x;i;i=son[i])
		st[++tp]=i;
	reverse(st+1,st+1+tp);
	return build(1,tp);
}
void change(int x,ll Val){
	w[x][2][1]+=Val-val[x];
	w[x][2][2]=w[x][2][1];
	if(maxp[x].size())
		w[x][0][1]=*maxp[x].rbegin();
	else
		w[x][0][1]=0;
	w[x][0][1]=max(w[x][0][1],w[x][2][1]);
	val[x]=Val;
	int u,v;
	for(int i=x;i;i=fa[i]){
		if(fa[i]&&s[fa[i]][0]!=i&&s[fa[i]][1]!=i){
			v=i;
			u=fa[i];
			maxp[u].erase(maxp[u].find(mul[v][0][1]));
			w[u][2][1]-=mul[v][0][2];
			
			update(i);
			
			maxp[u].insert(mul[v][0][1]);
			w[u][0][1]=*maxp[u].rbegin();
			w[u][2][1]+=mul[v][0][2];
			w[u][2][2]=w[u][2][1];
			w[u][0][1]=max(w[u][0][1],w[u][2][1]);
		}
		else 
			update(i);
	}
}
ll Query(int x){
	Matrix tmp;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			tmp[i][j]=0;
	if(son[x]==0)
		return max(0ll,val[x]);
	if(s[x][0])
		tmp=mul[s[x][0]]*w[x];
	else
		tmp=w[x];
	for(int i=x;fa[i]&&(s[fa[i]][0]==i||s[fa[i]][1]==i);i=fa[i]){
		int u=fa[i];
		if(s[u][1]==i){
			if(s[u][0]||son[u]==0)
				tmp=mul[s[u][0]]*w[u]*tmp;
			else
				tmp=w[u]*tmp;
		}
	}
	return tmp[0][1];
}
int n,m,u,v;
char opt[4];
int main(){
	SF("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		SF("%lld",&val[i]);
		w[i][2][1]=w[i][2][2]=w[i][0][1]=val[i];
		w[i][1][0]=w[i][1][2]=w[i][2][0]=-INF;
	}
	for(int i=1;i<n;i++){
		SF("%d%d",&u,&v);
		add_edge(u,v);
	}
	dfs(1);
	int rt=build_tree(1);
	for(int i=1;i<=m;i++){
		SF("%s",opt);
		if(opt[0]=='Q'){
			SF("%d",&u);
			PF("%lld
",Query(u));
		}
		else{
			SF("%d%d",&u,&v);
			change(u,v);
		}
	}
}