题目

分析

首先，将这些节点按dfs序建一棵线段树。

因为按dfs序，所以在同一子树上的节点会放在线段树相邻的位置。

发现，对于一个位置x，它的权值只会对以x为根的子树造成影响。

当修改x时，用w[x]更新子树x的最大值，

接着从x向上跳，用w[fa[x]]更新子树fa[x]-子树x最大值，

因为当用w[fa[x]]来更新过子树fa[x]-子树x时，再用它更新就会没有意义，所以打个标记，不再更新。这样就最多只会更新n次。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

const int N=100005;

using namespace std;

int d[N],aft[N],fa[N],mx[N*10],son[N],size[N],n,m,last[N*2],next[N*2],to[N*2],tot,v1[N],ans,end[N],lazy[N*10];

int bz[N];

int bj(int x,int y)

{

	next[++tot]=last[x];

	last[x]=tot;

	to[tot]=y;

}

int down(int v)

{

	if(!lazy[v]) return 0;

	lazy[v*2]=max(lazy[v],lazy[v*2]);

	lazy[v*2+1]=max(lazy[v],lazy[v*2+1]);

	mx[v*2]=max(mx[v*2],lazy[v]);

	mx[v*2+1]=max(mx[v*2+1],lazy[v]);

}

int dg(int x)

{

	d[++tot]=x;

	aft[x]=tot;

	for(int i=last[x];i;i=next[i])

	{

		int j=to[i];

		if(j!=fa[x])

		{

			fa[j]=x;

			dg(j);

			end[j]=tot;

		}

	}

}

int change(int v,int l,int r,int x,int y,int z)

{

	if(x>y && x && y) return 0;

	if(l==x && y==r)

	{

		mx[v]=max(mx[v],z);

		lazy[v]=max(lazy[v],z);

		return 0;

	}

	down(v);

	int mid=(l+r)/2;

	if(y<=mid) change(v*2,l,mid,x,y,z);

	else

	if(x>mid) change(v*2+1,mid+1,r,x,y,z);

	else change(v*2,l,mid,x,mid,z),change(v*2+1,mid+1,r,mid+1,y,z);

	mx[v]=max(mx[v*2],mx[v*2+1]);

}

int find(int v,int l,int r,int x)

{

	if(l==r) return mx[v];

	down(v);

	int mid=(l+r)/2,j;

	if(x<=mid) j=find(v*2,l,mid,x);

	else j=find(v*2+1,mid+1,r,x);

	mx[v]=max(mx[v*2],mx[v*2+1]);

	return j;

}

int up(int x)

{

	if(!fa[x]) return 0;

	change(1,1,tot,max(aft[fa[x]],1),aft[x]-1,v1[fa[x]]);

	change(1,1,tot,end[x]+1,end[fa[x]],v1[fa[x]]);

	if(!bz[x]) up(fa[x]);

	bz[x]=true;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) scanf("%d",&v1[i]);

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

		bj(x,y);

		bj(y,x);

	}

	tot=0;

	dg(1);

	end[1]=tot;

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

	{

		char c=getchar();

		int x;

		while(c!='Q' && c!='M') c=getchar();

		if(c=='M')

		{

			scanf("odify %d",&x);

			change(1,1,tot,aft[x],end[x],v1[x]);

			up(x);

		}

		else

		{

			scanf("uery %d",&x);

			ans=find(1,1,tot,aft[x]);

			printf("%d\n",(ans)?ans:-1);

		}

	}

}

巴特西

【GDOI2017模拟12.9】最近公共祖先

题目

分析

最新文章

热门文章