hdu 5044 树链剖分

转载：http://blog.csdn.net/qinzhenhua100/article/details/39716851

二种操作，一种更新结点值，一种更新路径值，最后输出更改后的结点值和路径值。

对于区间[a,b]，区间的每个值加上c，可以用一个数组标记，ans[a]+=c,ans[b+1]-=c;然后下标从a，遍历到b，把所有的ans[]值加上，就等于当前结点修改后的值。注意两点，一是手动扩栈，二是最终的结果用64位。

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

#define N 100010

struct pp

{

	int u,v;

}ed[N];

struct node

{

	int u,v,next;

}bian[N*2];

int e,id,dep[N],son[N],father[N],sz[N],ti[N],mark1[N],mark2[N],top[N],head[N];

__int64 a[N],b[N],ans1[N],ans2[N];

void add(int u,int v)

{

	bian[e].u=u;

	bian[e].v=v;

	bian[e].next=head[u];

	head[u]=e++;

}

void dfs1(int u,int fa)

{

	int i,v;

     dep[u]=dep[fa]+1; son[u]=0;   father[u]=fa; sz[u]=1;

	 for(i=head[u];i!=-1;i=bian[i].next)

	 {

		 v=bian[i].v;

		 if(v==fa) continue;

		 dfs1(v,u);

		 sz[u]+=sz[v];

		 if(sz[son[u]]<sz[v])

			 son[u]=v;

	 }

}

void dfs2(int u,int fa)

{

	int i,v;

	ti[u]=id++;

	mark1[id-1]=u;

	top[u]=fa;

	if(son[u]!=0)

		dfs2(son[u],fa);

	for(i=head[u];i!=-1;i=bian[i].next)

	{

		v=bian[i].v;

		if(v==father[u]||v==son[u])

			continue;

		dfs2(v,v);

	}

}

void getnode(int u,int v,int k)

{

	while(top[u]!=top[v])

	{

		if(dep[top[u]]>dep[top[v]])

			swap(u,v);

		a[ti[top[v]]]+=k;

		a[ti[v]+1]-=k;

		v=father[top[v]];

	}

	if(ti[u]>ti[v])

		swap(u,v);

	a[ti[u]]+=k;

	a[ti[v]+1]-=k;

}

void getedge(int u,int v,int k)

{

	while(top[u]!=top[v])

	{

		if(dep[top[u]]>dep[top[v]])

			swap(u,v);

		b[ti[top[v]]]+=k;

		b[ti[v]+1]-=k;

		v=father[top[v]];

	}

	if(ti[u]>ti[v])

		swap(u,v);

	if(u!=v)

	{

		b[ti[u]+1]+=k;

		b[ti[v]+1]-=k;

	}

}

int main()

{

	int t,cnt=1,n,m,i,u,v,k;

	__int64 s;

	char str[10];

	scanf("%d",&t);

	while(t--)

	{

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

	  memset(a,0,sizeof(a));

	  memset(head,-1,sizeof(head));

	  memset(b,0,sizeof(b));

	  e=0;

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

	  {

		  scanf("%d%d",&ed[i].u,&ed[i].v);

		  add(ed[i].u,ed[i].v);

		  add(ed[i].v,ed[i].u);

	  }

	  sz[0]=0; id=1; dep[1]=0;

	  dfs1(1,1);

	  dfs2(1,1);

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

	  {

		  scanf("%s%d%d%d",str,&u,&v,&k);

		  if(strcmp(str,"ADD1")==0)

		       getnode(u,v,k);

		  else

			  getedge(u,v,k);

	  }

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

	  {

		  if(dep[ed[i].u]<dep[ed[i].v])

			  mark2[ti[ed[i].v]]=i;

		  else

			  mark2[ti[ed[i].u]]=i;

	  }

	  printf("Case #%d:\n",cnt++);

	  s=0;

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

	  {

          s+=a[i];

		  ans1[mark1[i]]=s;

	  }

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

	  {

		  if(i==1)

			  printf("%I64d",ans1[i]);

		  else

			  printf(" %I64d",ans1[i]);

	  }

	  printf("\n");

	  s=0;

	  for(i=2;i<=n;i++)

	  {

		  s+=b[i];

          ans2[mark2[i]]=s;

	  }

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

	  {

		  if(i==1)

			  printf("%I64d",ans2[i]);

		  else

			  printf(" %I64d",ans2[i]);

	  }

	  printf("\n");

	}

	return 0;

}

巴特西

hdu 5044 树链剖分

最新文章

热门文章