BZOJ1036: [ZJOI2008]树的统计Count
? 解题记录 ? ? BZOJ ? ? 树链剖分 ? ? 线段树 ? ? 补档计划第一期 ?    2018-01-28 11:04:37    424    0    0

Description

  一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身

Input

  输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有
一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整数q,表示操作
的总数。接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。

Output

  对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

Sample Output

4

1

2

2

10

6

5

6

5

16

树链剖分模板题,套一个线段树。只是维护两个信息,一个区间和、一个区间最值。代码内含良心注释。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=30000+100;
int node_w[maxn];
int n;

struct edge
{
	int u,v;
	int next;
}e[maxn*2];
int head[maxn];
int depth[maxn];
int fa[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
int tid[maxn];
int rank[maxn];//映射tid到图编号 
int pos;//tid编号的累加 
int edc;

void adde(int u,int v)
{
	e[edc].u=u;
	e[edc].v=v;
	e[edc].next=head[u];
	head[u]=edc++;
}

void dfs1(int u,int p)//寻找重儿子 
{
	depth[u]=depth[p]+1;
	siz[u]=1;
	fa[u]=p;
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=p)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(son[u]==-1 || siz[v] > siz[son[u]])
			{
				son[u]=v;
			}
		}
	}
}

void dfs2(int u,int tp)//链接 
{
	top[u]=tp;
	tid[u]=++pos;
	rank[tid[u]]=u;
	if(son[u]==-1) //如果为叶子节点
		 return;
	dfs2(son[u],tp);
	for(int i=head[u];i!=-1;i=e[i].next)//重新开链 
	{
		int v=e[i].v;
		if(v!=son[u] && v!=fa[u])
			dfs2(v,v);
	}
}

struct seg
{
	int l,r;
	int sum;
	int mx;
}snode[maxn*4];

void pushup(int now)
{
	snode[now].sum=snode[now*2].sum+snode[now*2+1].sum;
	snode[now].mx=max(snode[now*2].mx,snode[now*2+1].mx);
}

void build_tree(int l,int r,int rt)
{
	snode[rt].l=l;snode[rt].r=r;
	if(l==r)
		{
			snode[rt].sum=node_w[rank[l]];//线段树为tid 把tid转换为原编号取权值
			snode[rt].mx=node_w[rank[l]];
			return; 
		}
	int m=(l+r)/2;
	build_tree(l,m,rt*2);
	build_tree(m+1,r,rt*2+1);
	pushup(rt);
}

void update(int k,int nw,int rt)
{
	int tl=snode[rt].l,tr=snode[rt].r;
	if(tl==k && tr==k)
		{
			snode[rt].sum=snode[rt].mx=nw;
			return;
		}
	int mid=(tl+tr)/2;
	if(k<=mid)	update(k,nw,rt*2);
	else update(k,nw,rt*2+1);
	pushup(rt);
}

int querymax(int l,int r,int rt)
{
	int tl=snode[rt].l,tr=snode[rt].r;
	if(tl==l && tr==r)
			return snode[rt].mx;
	int mid=(tl+tr)/2;
	if(r<=mid)	return querymax(l,r,rt*2);
	else if(l>mid) return querymax(l,r,rt*2+1);
	else return max(querymax(l,mid,rt*2),querymax(mid+1,r,rt*2+1));
}

int querysum(int l,int r,int rt)
{
	int tl=snode[rt].l,tr=snode[rt].r;
	if(tl==l && tr==r)
			return snode[rt].sum;
	int mid=(tl+tr)/2;
	if(r<=mid)	return querysum(l,r,rt*2);
	else if(l>mid) return querysum(l,r,rt*2+1);
	else return querysum(l,mid,rt*2)+querysum(mid+1,r,rt*2+1);
}

int getmax(int a,int b)
{
    int ans=-50000;
    while(top[a]!=top[b])
    {
        if(depth[top[a]]<depth[top[b]])
            swap(a,b);
            
        ans = max(ans,querymax(tid[top[a]],tid[a],1));
        a = fa[top[a]];
    }
    if(depth[a] > depth[b]) swap(a,b);
    return max(ans,querymax(tid[a],tid[b],1));
}

int getsum(int a,int b)
{
    int ans=0;
    while(top[a]!=top[b])
    {
        if(depth[top[a]]<depth[top[b]])
            swap(a,b);
            
        ans += querysum(tid[top[a]],tid[a],1);
        a = fa[top[a]];
    }
    if(depth[a] > depth[b]) swap(a,b);
    return ans+querysum(tid[a],tid[b],1);
}

int main()
{
	memset(head,-1,sizeof(head));
	memset(son,-1,sizeof(son));
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)	
		{
			int a,b;
			scanf("%d%d",&a,&b);
			adde(a,b);
			adde(b,a);
		}
	for(int i=1;i<=n;i++)
		{
			int a;
			scanf("%d",&a);
			node_w[i]=a;
		}
	dfs1(1,0);
	dfs2(1,1);
	build_tree(1,n,1);
	int t;
	scanf("%d",&t);
	char comm[20];
	while(t--)
	{
		scanf("%s",comm);
		if(strcmp(comm,"QMAX")==0)
			{
				int a,b;
				scanf("%d%d",&a,&b);
				printf("%d\n",getmax(a,b));
			}
		if(strcmp(comm,"QSUM")==0)
			{
				int a,b;
				scanf("%d%d",&a,&b);
				printf("%d\n",getsum(a,b));
			}
		if(strcmp(comm,"CHANGE")==0)
			{
				int a,b;
				scanf("%d%d",&a,&b);
				update(tid[a],b,1);
			}		
	}
	return 0;
}

上一篇: HDU2874 Connections between cities

下一篇: BZOJ1821: [JSOI2010]Group 部落划分 Group

424 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航