There is simple O(N+M) algo (core part is like 5 lines), and it's "online" (no preprocessing of queries required)

Edited by author 10.06.2026 04:20

Don't forget about long long int!

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, BLOCK = 320;

int n, m, a[100001], p[100001], idx[100001], order[100001], lb[100001], rb[100001]; // lb and rb are indexed by bfs order, not vertex
bool mark[100001];
vector<int> g[100001];

struct coolsqrt { // sqrt decomposition
    int f[100001], t[100001];
    void init() { for(int i = 1; i <= n; i++) f[i] = a[order[i]]; }
    void update(int l, int r, int v) {
        for(int i = l; i % BLOCK; i++) {
            f[i] = (f[i]+v)%MOD;
            if(i == r) return;
        }
        int block = l/BLOCK + 1;
        while(block < r/BLOCK) t[block++] += v, t[block] %= MOD;
        for(int i = BLOCK*(r/BLOCK); i <= r; i++) f[i]  = (f[i]+v)%MOD;
    }
    int query(int i) { return (f[i] + t[i/BLOCK])%MOD; }
    void putin() { for(int i = 1; i <= n; i++) cout << query(i) << ' '; cout << endl; }
} coolsqrt;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1,u,v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    for(int i = 1, u = q.front(); i <= n; i++, q.pop(), u = q.front()) {
        mark[u] = true;
        idx[u] = i;
        order[i] = u;
        for(int v: g[u]) if(!mark[v]) q.push(v), p[v] = u;
    }
    assert(q.empty());
    for(int i = 1; i <= n; i++) if(p[order[i]]) {
        if(!lb[p[order[i]]]) lb[p[order[i]]] = i;
        rb[p[order[i]]] = i;
    }
    coolsqrt.init();
    cin >> m;
    int inst,v;
    while(m--) {
        cin >> inst >> v;
        if(inst == 1) {
            coolsqrt.update(idx[p[v]], idx[p[v]], coolsqrt.query(idx[v]));
            coolsqrt.update(lb[v], rb[v], coolsqrt.query(idx[v]));
            // coolsqrt.putin();
        } else {
            cout << coolsqrt.query(idx[v]) << endl;
        }
    }
    // for(int i = 1; i <= n; i++) cout << order[i] << ' ';
    // cout << endl;
    // for(int i = 1; i <= n; i++) cout << lb[i] << ' ' << rb[i] << endl;
}

Edited by author 01.09.2016 20:03

Edited by author 01.09.2016 20:03

Why Runtime Error?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    unsigned short n, m;
    scanf("%hu", &n);
    vector <unsigned long long> bytes(n);
    vector <vector<unsigned short> > red(n);
    for(unsigned short i=0;i<n;i++) scanf("%llu", &bytes[i]);
    for(unsigned short i=1;i<n;i++) {
        unsigned short x, y;
        scanf("%hu %hu", &x, &y);
        red[x-1].push_back(y);
        red[y-1].push_back(x); }
    if(n>1) {
        for(unsigned short i=0;i<red.size();i++) sort(red[i].begin(), red[i].end());
        for(unsigned short i=0;i<red.size();i++) {
            for(unsigned short j=0;j<red[i].size()-1;j++) {
                if(red[i][j]==red[i][j+1]) {
                    for(unsigned short pos=j+1;pos<red[i].size()-1;pos++) red[i][pos] = red[i][pos+1];
                    red[i].pop_back(); }
            }
        }
    }
    scanf("%hu", &m);
    for(int i=0;i<m;i++) {
        unsigned short v, t;
        scanf("%hu %hu", &t, &v);
        if(t==1) {
            for(unsigned j=0;j<red[v-1].size();j++) bytes[red[v-1][j]-1] += bytes[v-1]; }
        if(t==2) printf("%llu\n", bytes[v-1]%1000000007); }
}

Input:

7
1 1 1 1 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
9
1 1
1 1
1 1
1 1
1 1
1 6
2 2
1 2
2 7

output:
7
8

I used segment tree, but got wa on testcase 6

If you get WA on test #8, don't forget about mod = 1000000007 :)

Hello everyone. I always receive time limit on Test №21. Could you give any hints? Maybe  this task requires special data structure (I try to represent tree as list of edges or adjacency list) or there is interesting algorythm? Thanks for reading.

Кт-т упрлс тк услв псть