洛谷 P3178 [HAOI2015]树上操作

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

输出格式：
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

输入输出样例

输入样例#1：
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
输出样例#1：
6
9
13
说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

树剖模板题

#include <cstdio>
#include <iostream>
#define N 100010
#define int long long 
using namespace std;
int n,m;
int val[N];
int mp[N];
int dcnt;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct EDGE{
    int to,nex;
}ed[N*2];
struct NODE{
    int fa,son,sz,dep,top,s,e;
}tr[N];
struct tree{
    int l,r;
    int sum;
    int lazy;
}tree[N*8];
int tot;
int head[N*2];
inline void add(int x,int y){
    ++tot;
    ed[tot].nex=head[x];
    head[x]=tot;
    ed[tot].to=y;
}
void dfs1(int u){
    tr[u].sz=1;
    for(int i=head[u];i;i=ed[i].nex)
     if(ed[i].to!=tr[u].fa){
         tr[ed[i].to].fa=u;
         tr[ed[i].to].dep=tr[u].dep+1;
         dfs1(ed[i].to);
         tr[u].sz+=tr[ed[i].to].sz;
         if(tr[ed[i].to].sz>tr[tr[u].son].sz)
            tr[u].son=ed[i].to;
     }
}
void dfs2(int u,int top){
    tr[u].top=top;
    tr[u].s=++dcnt;
    mp[dcnt]=u;//反向映射
    if(tr[u].son){
        dfs2(tr[u].son,top);
        for(int i=head[u];i;i=ed[i].nex)
            if(ed[i].to!=tr[u].fa&&ed[i].to!=tr[u].son)
              dfs2(ed[i].to,ed[i].to);
    }
    tr[u].e=dcnt;
}
inline void update(int b){
    tree[b].sum=tree[b*2].sum+tree[b*2+1].sum;
}
void build(int l,int r,int b){
    tree[b].l=l;
    tree[b].r=r;
    tree[b].lazy=0;
    if(l==r){
        tree[b].sum=val[mp[l]];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,b*2);
    build(mid+1,r,b*2+1);
    update(b);
}
inline void pushdown(int b){
    if(tree[b].lazy){
        if(tree[b].l!=tree[b].r)
        {
            tree[b*2].lazy+=tree[b].lazy;
            tree[b*2+1].lazy+=tree[b].lazy;        
            tree[b*2].sum+=(tree[b*2].r-tree[b*2].l+1)*tree[b].lazy;
            tree[b*2+1].sum+=(tree[b*2+1].r-tree[b*2+1].l+1)*tree[b].lazy;        
        }
        tree[b].lazy=0;    
    }
    return ;
}
void Add(int x,int y,int val,int k){
    if(x>y) swap(x,y);
    if(tree[k].r<x || tree[k].l>y) return;
    if(x<=tree[k].l && y>=tree[k].r){
        tree[k].lazy+=val;
        tree[k].sum+=val*(tree[k].r-tree[k].l+1);
        return;
    }
    pushdown(k);
    Add(x,y,val,2*k);
    Add(x,y,val,2*k+1);
    tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
}
int he(int x,int y,int k){
    if(x==tree[k].l && y==tree[k].r){
        return tree[k].sum;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)>>1;
    if(y<=mid){
  return he(x,y,2*k);}
    if(x>mid){
  return he(x,y,2*k+1);}
    return he(x,mid,2*k)+he(mid+1,y,2*k+1);
}
int Find_Sum(int x,int y){
    int f1=tr[x].top;
    int f2=tr[y].top;
    int ans=0;
    while(f1!=f2){
        if(tr[f1].dep<tr[f2].dep) swap(x,y),swap(f1,f2);
        ans+=he(tr[f1].s,tr[x].s,1);
        x=tr[f1].fa;
        f1=tr[x].top;
    }
    if(tr[x].dep<tr[y].dep){
         ans+=he(tr[x].s,tr[y].s,1);
    }
    else  ans+=he(tr[y].s,tr[x].s,1);
     return ans;

}
main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
    for(int i=2;i<=n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(1);dfs2(1,1);
    build(1,n,1);
 for(int i=1;i<=m;i++){
     int k,x,y;
        scanf("%lld",&k);
        switch(k){
            case 1: scanf("%lld%lld",&x,&y);Add(tr[x].s,tr[x].s,y,1);break;
            case 2: scanf("%lld%lld",&x,&y);Add(tr[x].s,tr[x].e,y,1);break;
            case 3: scanf("%lld",&x);printf("%lld\n",Find_Sum(x,1));break;
        }
    }
    return 0;
}