【Luogu4719】动态dp

题面

题解

等下发链接

代码：
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 100100

#define inf 1ll<<60

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int dfn[MAX],size[MAX],hson[MAX],top[MAX],bot[MAX],fa[MAX],ln[MAX],tim;

int V[MAX],n,m;

void dfs1(int u,int ff)

{

	fa[u]=ff;size[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dfs1(v,u);size[u]+=size[v];

		if(size[v]>size[hson[u]])hson[u]=v;

	}

}

void dfs2(int u,int tp)

{

	top[u]=tp;dfn[u]=++tim;ln[tim]=u;

	if(hson[u])dfs2(hson[u],tp),bot[u]=bot[hson[u]];

	else bot[u]=u;

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=fa[u]&&e[i].v!=hson[u])

			dfs2(e[i].v,e[i].v);

}

ll f[MAX][2];

void dp(int u,int ff)

{

	f[u][1]=V[u];

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dp(v,u);

		f[u][0]+=max(f[v][0],f[v][1]);

		f[u][1]+=f[v][0];

	}

}

struct Matrix{ll s[2][2];}t[MAX<<2],tmp[MAX];

Matrix operator*(Matrix a,Matrix b)

{

	Matrix ret;

	ret.s[0][0]=max(a.s[0][0]+b.s[0][0],a.s[0][1]+b.s[1][0]);

	ret.s[0][1]=max(a.s[0][0]+b.s[0][1],a.s[0][1]+b.s[1][1]);

	ret.s[1][0]=max(a.s[1][0]+b.s[0][0],a.s[1][1]+b.s[1][0]);

	ret.s[1][1]=max(a.s[1][0]+b.s[0][1],a.s[1][1]+b.s[1][1]);

	return ret;

}

void Build(int now,int l,int r)

{

	if(l==r)

	{

		int u=ln[l];int g0=0,g1=V[u];

		for(int i=h[u];i;i=e[i].next)

			if(e[i].v!=fa[u]&&e[i].v!=hson[u])

				g0+=max(f[e[i].v][0],f[e[i].v][1]),g1+=f[e[i].v][0];

		tmp[l]=t[now]=(Matrix){g0,g0,g1,-inf};

		return;

	}

	int mid=(l+r)>>1;

	Build(lson,l,mid);Build(rson,mid+1,r);

	t[now]=t[lson]*t[rson];

}

void Modify(int now,int l,int r,int p)

{

	if(l==r){t[now]=tmp[l];return;}

	int mid=(l+r)>>1;

	if(p<=mid)Modify(lson,l,mid,p);

	else Modify(rson,mid+1,r,p);

	t[now]=t[lson]*t[rson];

}

Matrix Query(int now,int l,int r,int L,int R)

{

	if(L==l&&r==R)return t[now];

	int mid=(l+r)>>1;

	if(R<=mid)return Query(lson,l,mid,L,R);

	if(L>mid)return Query(rson,mid+1,r,L,R);

	return Query(lson,l,mid,L,mid)*Query(rson,mid+1,r,mid+1,R);

}

Matrix GetMat(int x){return Query(1,1,n,dfn[top[x]],dfn[bot[x]]);}

void Modify(int u,int w)

{

	tmp[dfn[u]].s[1][0]+=w-V[u],V[u]=w;

	while(u)

	{

		Matrix a=GetMat(top[u]);Modify(1,1,n,dfn[u]);

		Matrix b=GetMat(top[u]);

		u=fa[top[u]];if(!u)break;

		tmp[dfn[u]].s[0][1]=(tmp[dfn[u]].s[0][0]+=max(b.s[0][0],b.s[1][0])-max(a.s[0][0],a.s[1][0]));

		tmp[dfn[u]].s[1][0]+=b.s[0][0]-a.s[0][0];

	}

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)V[i]=read();

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	dfs1(1,0);dfs2(1,1);dp(1,0);Build(1,1,n);

	while(m--)

	{

		int u=read(),w=read();

		Modify(u,w);Matrix ans=GetMat(1);

		printf("%lld\n",max(ans.s[0][0],ans.s[1][0]));

	}

	return 0;

}
巴特西

【Luogu4719】动态dp

题面

题解

最新文章

热门文章
