Pagini recente » Cod sursa (job #1559761) | Cod sursa (job #1564051) | Cod sursa (job #2924395) | Cod sursa (job #2649270) | Cod sursa (job #2924234)
#include <bits/stdc++.h>
#define L 100005
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
vector <int> G[L];
int lin_tree[L], pos_in_lin_tree[L], sons[L], bucket_sum[L], elem_sum[L], bucket_size, i1 = 1, n;
bool vis[L];
void DFS(int node){
vis[node] = true;
pos_in_lin_tree[node] = i1;
lin_tree[i1++] = node;
sons[node] = 1;
for (auto it : G[node])
if (!vis[it]){
DFS(it);
sons[node] += sons[it];
}
}
int main(){
int q, t, p, s, i, j, a, b, j1, j2, root = 1;
fin >> n >> q;
for (i = 1; i < n; i++){
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
DFS(root);
/**
for (i = 1; i <= n; i++)
cout << lin_tree[i] << " ";
cout << "\n";
for (i = 1; i <= n; i++)
cout << pos_in_lin_tree[i] << " ";
cout << "\n";
for (i = 1; i <= n; i++)
cout << sons[i] << " ";
cout << "\n";
**/
bucket_size = sqrt(n);
for (j = 0; j < q; j++){
fin >> t;
if (t == 1){
fin >> p >> s;
j1 = pos_in_lin_tree[p];
j2 = pos_in_lin_tree[p] + sons[p] - 1;
if (j2 - j1 + 1 <= bucket_size)
for (i = j1; i <= j2; i++)
elem_sum[i] += s;
else{
for (i = j1; i % bucket_size != 0; i++)
elem_sum[i] += s;
elem_sum[i] += s;
a = i;
for (i = j2; i % bucket_size != 1; i--)
elem_sum[i] += s;
elem_sum[i] += s;
b = i - 1;
for (i = a / bucket_size + 1; i <= b / bucket_size; i++)
bucket_sum[i] += s;
}
}
else{
fin >> s;
}
}
return 0;
}