Cod sursa(job #2924234)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 27 septembrie 2022 18:01:32
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#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;
}