【每日一题】dfs序专题,求和

求和

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

Solution





#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

vector<int> edge[N];
int tot, val[N], l[N], r[N];
ll sum[N];

void dfs(int u, int tmp) {
    l[u] = ++tot;
    for (auto& v : edge[u]) {
        if (v == tmp)    continue;
        dfs(v, u);
    }
    r[u] = tot;
}

int lowbit(int x) { return x & (-x); }
void update(int x, int y) {
    for (; x < N; x += lowbit(x))
        sum[x] += y;
}
ll query(int x) {
    ll res = 0;
    for (; x; x -= lowbit(x))
        res += sum[x];
    return res;
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read(), s = read();
        for (int i = 1; i <= n; ++i)    val[i] = read();
        for (int i = 1; i < n; ++i) {
            int u = read(), v = read();
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        dfs(s, 0);
        for (int i = 1; i <= n; ++i)
            update(l[i], val[i]);
        while (m--) {
            int op = read();
            if (op & 1) {
                int u = read(), x = read();
                update(l[u], x); //单点修改
            }
            else {
                int u = read();
                print(query(r[u]) - query(l[u] - 1)); // 区间查询
            }
        }
    }
    return 0;
}
每日一题 文章被收录于专栏

每日一题

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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 17:48
吉林大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-27 14:35
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-10 09:46
宁夏大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
3 收藏 评论
分享

全站热榜

正在热议