BZOJ1036: [ZJOI2008]树的统计Count

本文主要是介绍BZOJ1036: [ZJOI2008]树的统计Count，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. 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”的形式给出。

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

Data Constraint

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Solution

这是一道非常明显的树剖题
树剖就是把一棵树剖分成轻链和重链，放入线段树中处理各种信息，便于处理（查询和修改）树中路径上的值。

将树中的边分为：轻边和重边，定义size(X)为以X为根的子树的节点个数。令V为U的儿子节点中size值最大的节点，那么边(U,V)被称为重边，树中重边之外的边被称为轻边。

性质：轻边(U,V)，size(V)<=size(U)/2。

具体方法：
1.dfs一次，处理出每个点的子树大小（size），深度（dep），父亲（fa），重儿子（son）。
2.再dfs一次，因为在数据结构中一条重链是连续的一段，所以要重新编号及处理出每个点在的重链的顶端（top）。

 void dfs2(int x,int topp){w[x]=++totw; top[x]=topp;if (son[x]!=0)dfs2(son[x],top[x]);//沿着重链走，所以top不变for (int i=last[x];i!=0;i=side[i].next)if (side[i].y!=son[x] && side[i].y!=fa[x])dfs2(side[i].y,side[i].y);//新的一条链，这个点即顶端。}

3.当要查询两点间路径上的信息时，

若两点在同一条重链上，就可以直接查询。
若不在同一重链上，把深的点跳到其top的父亲，并计算它到top这段的值。最终两点一定会在一条重链上。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;#define N 30030
#define INF 0x7fffffffstruct edge
{int y,next;
};struct tr
{int ma,sum;
};tr tree[N*4];
edge side[N*2];
int size[N],last[N],fa[N],son[N],dep[N],num[N],top[N],w[N];
int n,m,tot,totw;
char ch[15];void add(int x,int y)
{++tot;side[tot].y=y;side[tot].next=last[x];last[x]=tot;
}void init()
{scanf("%d",&n);int x,y;memset(last,0,sizeof(last));for (int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}for (int i=1;i<=n;i++)scanf("%d",&num[i]);
}void dfs1(int x)
{size[x]=1; son[x]=0;for (int i=last[x];i!=0;i=side[i].next)if (side[i].y!=fa[x]){int j=side[i].y;fa[j]=x;dep[j]=dep[x]+1;dfs1(j);size[x]+=size[j];if (size[j]>size[son[x]]) son[x]=j;}
}void dfs2(int x,int topp)
{w[x]=++totw; top[x]=topp;if (son[x]!=0) dfs2(son[x],top[x]);for (int i=last[x];i!=0;i=side[i].next)if (side[i].y!=son[x] && side[i].y!=fa[x])dfs2(side[i].y,side[i].y);
}void change(int x,int l,int r,int po,int q)
{if (po==l && l==r){tree[x].ma=tree[x].sum=q;return;}int mid=(l+r)/2;if (po<=mid) change(x+x,l,mid,po,q);else change(x+x+1,mid+1,r,po,q);tree[x].sum=tree[x+x].sum+tree[x+x+1].sum;tree[x].ma=max(tree[x+x].ma,tree[x+x+1].ma);
}int qumax(int x,int l,int r,int s,int e)
{if (l==s && r==e) return tree[x].ma;int mid=(l+r)/2;if (e<=mid) return qumax(x+x,l,mid,s,e);else if (s>mid) return qumax(x+x+1,mid+1,r,s,e);else return max(qumax(x+x,l,mid,s,mid),qumax(x+x+1,mid+1,r,mid+1,e));
}int qusum(int x,int l,int r,int s,int e)
{if (l==s && r==e) return tree[x].sum;int mid=(l+r)/2;if (e<=mid) return qusum(x+x,l,mid,s,e);else if (s>mid) return qusum(x+x+1,mid+1,r,s,e);else return qusum(x+x,l,mid,s,mid)+qusum(x+x+1,mid+1,r,mid+1,e);
}void solmax(int x,int y)
{int mx=-INF;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);mx=max(mx,qumax(1,1,n,w[top[x]],w[x]));x=fa[top[x]];}if (dep[x]>dep[y]) swap(x,y);mx=max(mx,qumax(1,1,n,w[x],w[y]));printf("%d\n",mx);
}void solsum(int x,int y)
{int su=0;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);su+=qusum(1,1,n,w[top[x]],w[x]);x=fa[top[x]];}if (dep[x]>dep[y]) swap(x,y);su+=qusum(1,1,n,w[x],w[y]);printf("%d\n",su);
}int main()
{freopen("1036.in","r",stdin);freopen("1036.out","w",stdout);init();dfs1(1);dfs2(1,1);for (int i=1;i<=n;i++)change(1,1,n,w[i],num[i]);scanf("%d",&m);int x,y;for (int i=1;i<=m;i++){scanf("%s%d%d",ch,&x,&y);if (ch[0]=='C') change(1,1,n,w[x],y);elseif (ch[1]=='M') solmax(x,y);else solsum(x,y);}return 0;
}