BZOJ 4034: [HAOI2015]T2

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

6
9
13

HINT

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6 。

题解

计算贡献的思路。需要一个区间修改单点查询的数据结构，可以是线段树也可以是树状数组【普通的树状数组反过来用！>.<！】
把树按照dfs序分一下！
对于操作一，我们只需要给受到影响的点增加a就可以了，即x的子树，dfs序是连续的！
对于操作二，我们发现对受到影响的点的贡献可以分为两部分，一部分是和深度无关的，一部分是和深度有关的。我们分开计算！假设修改u为根的子树，计算对v的答案贡献。DeltaV=dist[v]d + (1-dist[u])d，可以发现前面是和v深度有关的，后面只和u的深度有关和v的深度是无关的！分开计算就行了。
对于操作三，那么我们只需要把深度有关的深度无关的加起来就行了！

#include<cstdio>
using namespace std;
const int Maxn=100005;
int dep[Maxn];
int dfn[Maxn],out[Maxn];
bool vis[Maxn];
int tot;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int a,int b){
        v=a;
        nxt=b;
    }
};
Edge e[Maxn*2+10];
int head[Maxn];
int nume;
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}
void dfs(int x){
    vis[x]=true;
    dfn[x]=++tot;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!vis[v]){
            dep[v]=dep[x]+1;
            dfs(v);
        }
    }
    out[x]=tot;
}
struct Btree{
    int left,right;
    long long sum;
    long long tag;
};
struct SegmentTree{
    Btree tree[Maxn*4];
    void build(int x,int left,int right){
        tree[x].left=left;
        tree[x].right=right;
        tree[x].sum=tree[x].tag=0;
        if (left==right){
        }else{
            int mid=(left+right)/2;
            build(x*2,left,mid);
            build(x*2+1,mid+1,right);
        }
    }
    inline void merge(int x){
        if (tree[x].left==tree[x].right) return;
        tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    }
    inline void clean(int x){
        if (tree[x].left==tree[x].right) return;
        if (tree[x].tag==0) return;
        long long tag=tree[x].tag;
        tree[x].tag=0;
        tree[x*2].sum+=(long long)(tree[x*2].right-tree[x*2].left+1)*tag;
        tree[x*2+1].sum+=(long long)(tree[x*2+1].right-tree[x*2+1].left+1)*tag;
        tree[x*2].tag+=tag;
        tree[x*2+1].tag+=tag;
    }
    void add(int x,int left,int right,long long val){
        //printf("Tree->%d\n",x);
        clean(x);
        if (left<=tree[x].left && tree[x].right<=right){
            tree[x].sum+=(long long)(tree[x].right-tree[x].left+1)*val;
            tree[x].tag+=val;
        }else{
            int mid=(tree[x].left+tree[x].right)/2;
            if (left<=mid) add(x*2,left,right,val);
            if (mid+1<=right) add(x*2+1,left,right,val);
            merge(x);
        }
    }
    long long query(int x,int left,int right){
        //printf("Tree->%d\n",x);
        clean(x);
        if (left<=tree[x].left && tree[x].right<=right){
            //printf("Sum:%lld\n",tree[x].sum);
            return tree[x].sum;
        }else{
            int mid=(tree[x].left+tree[x].right)/2;
            long long Ans=0;
            if (left<=mid) Ans+=query(x*2,left,right);
            if (mid+1<=right) Ans+=query(x*2+1,left,right);
            return Ans;
        }
    }
};
SegmentTree s1,s2;
long long num[Maxn];
int n,m;
int w,x,y;
int main(){
    scanf("%d%d",&n,&m);
    s1.build(1,1,n);
    s2.build(1,1,n);
    for (int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for (int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    dep[1]=1;
    dfs(1);
    for (int i=1;i<=n;i++) s1.add(1,dfn[i],out[i],num[i]);
    for (int i=1;i<=m;i++){
        scanf("%d",&w);
        if (w==1 || w==2) scanf("%d%d",&x,&y); else scanf("%d",&x);
        if (w==1)s1.add(1,dfn[x],out[x],y);
        if (w==2){
            s1.add(1,dfn[x],out[x],(long long)(1-dep[x])*y);
            s2.add(1,dfn[x],out[x],y);
        }
        if (w==3)printf("%lld\n",s1.query(1,dfn[x],dfn[x])+s2.query(1,dfn[x],dfn[x])*(long long)dep[x]);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include<cstdio>

using namespace std;

const int Maxn=100005;

int dep[Maxn];

int dfn[Maxn],out[Maxn];

bool vis[Maxn];

int tot;

struct Edge{

int v,nxt;

Edge(){}

Edge(int a,int b){

v=a;

nxt=b;

}

};

Edge e[Maxn*2+10];

int head[Maxn];

int nume;

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

e[++nume]=Edge(u,head[v]);

head[v]=nume;

}

void dfs(int x){

vis[x]=true;

dfn[x]=++tot;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (!vis[v]){

dep[v]=dep[x]+1;

dfs(v);

}

out[x]=tot;

}

struct Btree{

int left,right;

long long sum;

long long tag;

};

struct SegmentTree{

Btree tree[Maxn*4];

void build(int x,int left,int right){

tree[x].left=left;

tree[x].right=right;

tree[x].sum=tree[x].tag=0;

if (left==right){

}else{

int mid=(left+right)/2;

build(x*2,left,mid);

build(x*2+1,mid+1,right);

}

inline void merge(int x){

if (tree[x].left==tree[x].right) return;

tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;

}

inline void clean(int x){

if (tree[x].left==tree[x].right) return;

if (tree[x].tag==0) return;

long long tag=tree[x].tag;

tree[x].tag=0;

tree[x*2].sum+=(long long)(tree[x*2].right-tree[x*2].left+1)*tag;

tree[x*2+1].sum+=(long long)(tree[x*2+1].right-tree[x*2+1].left+1)*tag;

tree[x*2].tag+=tag;

tree[x*2+1].tag+=tag;

}

void add(int x,int left,int right,long long val){

//printf("Tree->%d\n",x);

clean(x);

if (left<=tree[x].left && tree[x].right<=right){

tree[x].sum+=(long long)(tree[x].right-tree[x].left+1)*val;

tree[x].tag+=val;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid) add(x*2,left,right,val);

if (mid+1<=right) add(x*2+1,left,right,val);

merge(x);

}

long long query(int x,int left,int right){

//printf("Tree->%d\n",x);

clean(x);

if (left<=tree[x].left && tree[x].right<=right){

//printf("Sum:%lld\n",tree[x].sum);

return tree[x].sum;

}else{

int mid=(tree[x].left+tree[x].right)/2;

long long Ans=0;

if (left<=mid) Ans+=query(x*2,left,right);

if (mid+1<=right) Ans+=query(x*2+1,left,right);

return Ans;

}

};

SegmentTree s1,s2;

long long num[Maxn];

int n,m;

int w,x,y;

int main(){

scanf("%d%d",&n,&m);

s1.build(1,1,n);

s2.build(1,1,n);

for (int i=1;i<=n;i++) scanf("%lld",&num[i]);

for (int i=1;i<n;i++){

scanf("%d%d",&x,&y);

addEdge(x,y);

}

dep[1]=1;

dfs(1);

for (int i=1;i<=n;i++) s1.add(1,dfn[i],out[i],num[i]);

for (int i=1;i<=m;i++){

scanf("%d",&w);

if (w==1 || w==2) scanf("%d%d",&x,&y); else scanf("%d",&x);

if (w==1)s1.add(1,dfn[x],out[x],y);

if (w==2){

s1.add(1,dfn[x],out[x],(long long)(1-dep[x])*y);

s2.add(1,dfn[x],out[x],y);

}

if (w==3)printf("%lld\n",s1.query(1,dfn[x],dfn[x])+s2.query(1,dfn[x],dfn[x])*(long long)dep[x]);

}

return 0;

}

WNJXYKの博客

喂你脚下有坑