记录编号	303719	评测结果	AAAAAWWWWW
题目名称	[HAOI 2015]树上操作	最终得分	50
用户昵称	Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	2.164 s
提交时间	2016-09-06 16:18:45	内存使用	25.66 MiB

#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define LL long long
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r 
using namespace std;
const int maxn=100001;
struct Edge{
    int to,next;
}e[maxn<<4];
struct Node{
    int date,lazy;
}a[maxn<<4];
int head[maxn],len,root[maxn],son[maxn],size[maxn],id[maxn],pos[maxn];
int deep[maxn],top[maxn],ra[maxn],cnt,n,m,Qx,Qy,v[maxn],res;
void Insert(int x,int y){//建边 
    len++;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void Dfs1(int);
//求size 以自己为根的包括自己的节点总数，son所有儿子中权值最大的儿子，即重儿子，deep 该节点的深度，root 该节点的父亲 
void Dfs2(int,int); 
//求ra  以x为根的子节点的结尾叶子节点 ，id  节点x在树链中的位置，top 节点x所在重链最上面的节点，如果x不在重链上，则top【x】=x,pos记录它本来的位置 
//两个Dfs求各个数组
void Update(int,int,int);//传递lazy值
void Build(int,int,int);//正式建树

int tree_query(int,int);
int Query(int,int);
void Query(int,int,int);//求任意节点到节点1的所有点的权值和 
 
void Change(int,int,int,int,int);//改变一个节点的权值，给此节点的权值+t
void add(int,int,int,int,int,int); //把某个节点x为根的子树中所有点的点权都增加a。
 
int main(){
    freopen("haoi2015_t2.in","r",stdin);
    freopen("haoi2015_t2.out","w",stdout);
    scanf("%d%d",&n,&m);//点数为n的树，以1为节点，m次操作
    deep[1]=1;
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);//每个节点的权值
    for(int i=1;i<n;i++){//n-1条边 
        int x,y;scanf("%d%d",&x,&y);
        Insert(x,y);Insert(y,x);
    } 
    Dfs1(1);
    Dfs2(1,1);
    Build(1,1,n); 
    int type,x,a;
    for(int i=1;i<=m;i++){
        scanf("%d",&type);
        if(type==1){//改变一个节点的权值，给此节点的权值+a
            scanf("%d%d",&x,&a);
            Change(id[x],a,1,1,n);
        }
        if(type==2){//把某个节点x为根的子树中所有点的点权都增加a。
            scanf("%d%d",&x,&a);
            add(id[x],ra[x],a,1,1,n); 
        }
        if(type==3){
            scanf("%d",&x);
            printf("%d\n",tree_query(1,x));
        }
    }
    //system("pause");
    return 0;
} 
void Dfs1(int x){
    size[x]=1;son[x]=0;
    for(int i=head[x];i;i=e[i].next){
        int p=e[i].to;
        if(p!=root[x]){
            root[p]=x;deep[p]=deep[x]+1;
            Dfs1(p);
            size[x]+=size[p];
            if(size[p]>size[son[x]])son[x]=p;
        }
    } 
}
void Dfs2(int x,int tp){
    top[x]=tp;id[x]=++cnt;pos[cnt]=x;
    if(son[x])Dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].next){
        int k=e[i].to;
        if(root[x]!=k && son[x]!=k)Dfs2(k,k);
    }
    ra[x]=cnt;
} 
void Build(int rt,int l,int r){
    if(l==r){
        a[rt].date=v[pos[l]];return;
    }
    int mid=(l+r)>>1;
    Build(lson);Build(rson);
    a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
}
void Update(int rt,int l,int r){
    int x=a[rt].lazy;
    int mid=(l+r)>>1;
    a[rt<<1].lazy+=x;a[rt<<1|1].lazy+=x;
    a[rt<<1].date+=x*(mid-l+1);a[rt<<1|1].date+=x*(r-mid);
    a[rt].lazy=0;
}
void Change(int x,int z,int rt,int l,int r){
    if(l==r){
        a[rt].date+=z;return;
    }
    int mid=(l+r)>>1;
    if(a[rt].lazy)Update(rt,l,r);
    if(x<=mid)Change(x,z,lson);
    else Change(x,z,rson);
    a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
}
void add(int s,int t,int z,int rt,int l,int r){
    if(s<=l && t>=r){a[rt].date+=(r-l+1)*z;a[rt].lazy+=z;return;}
    int mid=(l+r)>>1;
    if(a[rt].lazy)Update(rt,l,r);
    if(s<=mid)add(s,t,z,lson);
    if(t>mid)add(s,t,z,rson);
    a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
}
int tree_query(int x,int y){
    int fx=top[x],fy=top[y],ans=0;
    while(fx!=fy){
        if(deep[fx]<deep[fy]){swap(x,y);swap(fx,fy);}
        ans+=Query(id[fx],id[x]);
        x=root[fx];fx=top[x];
    }
    if(deep[x]>deep[y])swap(x,y);
    ans+=Query(id[x],id[y]);
    return ans;
}
int Query(int s,int t){
    Qx=s;Qy=t;res=0;
    Query(1,1,n);
    return res;
}
void Query(int rt,int l,int r){
    if(Qx<=l && Qy>=r){
        res+=a[rt].date;return;
    }
    int mid=(l+r)>>1;
    if(a[rt].lazy)Update(rt,l,r);
    if(Qx<=mid)Query(lson);
    if(Qy>mid)Query(rson);
    a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
}