求和(dfs序+树状数组)

求和

https://ac.nowcoder.com/acm/problem/204871

图片说明
思路:
最朴素的做法:维护一个dp[i]:以i为子树的所有结点和,然后对于每个节点更新,朴素的更新它父亲节点的值,但是,如果树是一个长链这个就超时了。
正解:
先dfs求一个dfs序,这样以i节点的子树都是在一段区间内,所以我们可以维护一下i的子树的数量,那么求以i为根的子树和就是[dfs(i) - 1,dfs(i) + son[i] - 1]区间和,dfs(i):i节点的dfs序。
子树的和用一个区间和就解决了,那么修改节点i的值无非就是单点更新,树状数组维护一下即可。
代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 10;
vector<int>G[maxn];
int tot,cnt[maxn];
int n,m,root;
int val[maxn],son[maxn],s[maxn];
void dfs(int u,int fu){
    son[u] = 1;
    cnt[u] = ++tot;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs(v,u);
            son[u] += son[v];
        }
    }
}
void update(int x,int v){
    for(; x <= maxn; x += (x & -x)){
        s[x] += v;
    }
}
int query(int x){
    int sum = 0;
    for(; x ; x -= (x & -x)){
        sum += s[x];
    }
    return sum;
}
void solved(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i = 1; i <= n; i++)scanf("%d",&val[i]);
    for(int i = 1; i < n; i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(root,0);
    for(int i = 1; i <= n; i++)update(cnt[i],val[i]);
    while(m--){
        int ins;scanf("%d",&ins);
        if(1 == ins){
            int a,x;scanf("%d%d",&a,&x);
            update(cnt[a],x);
        }else {
            int a;scanf("%d",&a);
            printf("%d\n",query(cnt[a] + son[a] - 1) - query(cnt[a] - 1));
        }
    }
}
int main(){
    solved();
    return 0;
}
牛客每日一题 文章被收录于专栏

牛客每日一题

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
5 2 评论
分享

全站热榜

正在热议