首页 > 代码库 > 数的统计count(bzoj1036)

数的统计count(bzoj1036)

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
/*
  第一次写树链剖分,大概就是把一棵树分成很多链,然后把这些链首尾相接,形成一个序列,然后再用其他数据结构维护这个序列。
  具体操作是把边分为轻边和重边,重边是某个节点与他的最大字数的根节点的连边,由重边构成的链叫重链。
  先说一下几个数组的意思:
  size[]数组,用来保存以x为根的子树节点个数
  top[]数组,用来保存当前节点的所在链的顶端节点
  son[]数组,用来保存重儿子
  dep[]数组,用来保存当前节点的深度
  fa[]数组,用来保存当前节点的父亲
  pos[]数组,用来保存树中每个节点剖分后的新编号
第一遍dfs:求出树每个结点的深度dep[x],其为根的子树大小size[x]
第二遍dfs:?根节点为起点,向下拓展构建重链
选择最大的一个子树的根继承当前重链
其余节点,都以该节点为起点向下重新拉一条重链
给每个结点分配一个位置编号,每条重链就相当于一段区间,用数据结构去维护。
把所有的重链首尾相接,放到同一个数据结构上,然后维护这一个整体即可

修改操作
1、单独修改一个点的权值
根据其编号直接在数据结构中修改就行了。
2、修改点u和点v的路径上的权值
(1)若u和v在同一条重链上
直接用数据结构修改pos[u]至pos[v]间的值。
(2)若u和v不在同一条重链上
一边进行修改,一边将u和v往同一条重链上靠,然后就变成了情况(1)。

查询操作
查询操作的分析过程同修改操作
*/
#include<cstdio>
#include<iostream>
#define N 300010
#define inf 1000000000
#define lson l,mid,now*2
#define rson mid+1,r,now*2+1
using namespace std;
int pos[N],son[N],top[N],dep[N],size[N],fa[N];
int head[N],v[N],n,m,sum[N*4],mx[N*4],sz;
struct node{
    int to,pre;
};node e[N*2];
void add(int i,int x,int y){
    e[i].pre=head[x];
    e[i].to=y;
    head[x]=i;
}
void dfs1(int x){
    size[x]=1;
    for(int i=head[x];i;i=e[i].pre){
        if(e[i].to==fa[x])continue;
        dep[e[i].to]=dep[x]+1;
        fa[e[i].to]=x;
        dfs1(e[i].to);
        size[x]+=size[e[i].to];
    }
}
void dfs2(int x,int ding){
    int k=0;sz++;
    pos[x]=sz;top[x]=ding;
    for(int i=head[x];i;i=e[i].pre)
        if(dep[e[i].to]>dep[x]&&size[e[i].to]>size[k])
             k=e[i].to;
    if(!k)return;
    dfs2(k,ding);
    for(int i=head[x];i;i=e[i].pre)
        if(dep[e[i].to]>dep[x]&&e[i].to!=k)
            dfs2(e[i].to,e[i].to);
}
void push_up(int now){
    sum[now]=sum[now*2]+sum[now*2+1];
    mx[now]=max(mx[now*2],mx[now*2+1]);
}
void change(int x,int y,int l,int r,int now){
    if(l==r){
        sum[now]=mx[now]=y;return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change(x,y,lson);
    else change(x,y,rson);
    push_up(now);
}
int quirysum(int x,int y,int l,int r,int now){
    if(l>=x&&r<=y)return sum[now];
    int mid=(l+r)>>1,tot=0;
    if(x<=mid)tot+=quirysum(x,y,lson);
    if(y>mid)tot+=quirysum(x,y,rson);
    return tot;
}
int quirymx(int x,int y,int l,int r,int now){
    if(l>=x&&r<=y)return mx[now];
    int mid=(l+r)>>1,tot=-inf;
    if(x<=mid)tot=max(tot,quirymx(x,y,lson));
    if(y>mid)tot=max(tot,quirymx(x,y,rson));
    return tot;
}
int solvesum(int x,int y){
    int tot=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        tot+=quirysum(pos[top[x]],pos[x],1,n,1);
        x=fa[top[x]];
    }
    if(pos[x]>pos[y])swap(x,y);
    tot+=quirysum(pos[x],pos[y],1,n,1);
    return tot;
}
int solvemx(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,quirymx(pos[top[x]],pos[x],1,n,1));
        x=fa[top[x]];
    }
    if(pos[x]>pos[y])swap(x,y);
    mx=max(mx,quirymx(pos[x],pos[y],1,n,1));
    return mx;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        add(i*2-1,x,y);add(i*2,y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    dfs1(1);dfs2(1,1);
    for(int i=1;i<=n;i++)change(pos[i],v[i],1,n,1);
    scanf("%d",&m);char ch[10];
    while(m--){
        int x,y;scanf("%s%d%d",ch,&x,&y);
        if(ch[0]==C){v[x]=y;change(pos[x],y,1,n,1);}
        else {
            if(ch[1]==M)printf("%d\n",solvemx(x,y));
            else printf("%d\n",solvesum(x,y));
        }
    }
    return 0;
}

最后贴一个很好的ppt:http://wenku.baidu.com/link?url=SGLjpJtYbJ0HxDYlU_GMXE1qCFS0gbmpDGWPxI7mQuNAsJP0y872mNKwpZ8P054g5XMhFGZbMUjZvN5hcnxFFUEfGBj6-tnkpnJvnVSlqGS

数的统计count(bzoj1036)