słowacki powraca na 100

#ifndef _zad_h_
#define _zad_h_
#include<vector>
#include<tuple>
using namespace std;

int tree[1 << 20], M = 1, nr = -1;
vector<int> pre, pos;
int up[100007][20];

vector<pair<int, int>> G[100007];
void DFS(int a, int fat, int d){
  pre[a] = ++nr;
  tree[pre[a] + M] = d;
  up[a][0] = fat;
  for(int i = 1;i < 20;i++)
    up[a][i] = up[up[a][i - 1]][i - 1];
  for(auto i : G[a])
    if(i.first != fat)
      DFS(i.first, a, d + i.second);
  pos[a] = nr;
}
bool ancestor(int a, int b){
  return pre[a] <= pre[b] && pos[a] >= pos[b];
}
void init(vector<tuple<int, int, int>> e){
  int n = e.size() + 1, m = e.size();
  pre.resize(n + 7); pos.resize(n + 7);
  while(M <= n)
    M *= 2;
  for(int i = 0, v, u, w;i < m;i++){
    tie(v, u, w) = e[i];
    G[v].emplace_back(u, w);
    G[u].emplace_back(v, w);
  }
  DFS(1, 1, 0);
}
int LCA(int a, int b){
  if(ancestor(a, b))
    return a;
  if(ancestor(b, a))
    return b;
  for(int i = 19;i >= 0;i--)
    if(!ancestor(up[a][i], b))
      a = up[a][i];
  return up[a][0];
}
int spacer(int v, int d = 0){
  v = pre[v] + M;
  while(v){
    d += tree[v];
    v /= 2;
  }
  return d;
}
int distance(int a, int b){
  return spacer(a) + spacer(b) - 2 * spacer(LCA(a, b));
}
void change(int a, int b, int c){
  int v = ancestor(a, b) ? b : a;
  c -= abs(spacer(a) - spacer(b));
  int p = pre[v] + M, k = pos[v] + M;
  while(p <= k && p > 0 && k > 0){
    if(p % 2 == 1) tree[p++] += c;
    if(k % 2 == 0) tree[k--] += c;
    p /= 2;
    k /= 2;
  }
}

#endif
/*
JESTEM Z SIEBIE DUMNY
*/