#include <bits/stdc++.h>
#include "infection.h"
using namespace std;

#define pb push_back
using ll = long long;
#define int ll
using pi = array<int, 2>;
using ti = array<int, 3>;

const int INF = 1e18;

struct Meet {
  int d = INF, id1, id2;
  bool operator<(const Meet& b) const {
    return (ti{d, id1, id2} < ti{b.d, b.id1, b.id2});
  }
};

// incepem la ziua 0
struct Arbore {
  int max_id = -1;
  
  // pos[stanga / dreapta][neinfectat / infectat]
  array<array<set<pi>, 2>, 2> pos;
  vector<bool> is_active;
  vector<int> id_dir, id_pos, when_infected;
  
  int exact_pos(int i, int j, int p) {
    auto it = pos[i][j].lower_bound({p, -1});
    if (it == pos[i][j].end() || (*it)[0] != p) {
      return -1;
    }
    return (*it)[1];
  }
  int bigger_pos(int i, int j, int p) {
    auto it = pos[i][j].lower_bound({p, -1});
    if (it == pos[i][j].end()) {
      return -1;
    }
    return (*it)[1];
  }
  int smaller_pos(int i, int j, int p) {
    auto it = pos[i][j].upper_bound({p, max_id});
    if (it == pos[i][j].begin()) {
      return -1;
    }
    --it;
    return (*it)[1];
  }
  
  Meet find_meet(int d, int id) {
    assert(is_active[id]);
    
    int dir = id_dir[id], p = id_pos[id], inf = (when_infected[id] != INF);
    if (dir) {
      // p + d + k = p2 - d - k
      // p + 2d + 2k = p2
      // p + 2d = p2 - 2k
      // k = (p2 - p - 2d) / 2
      // deci p2 trb sa fie mai mare decat p+2d
      int id2 = bigger_pos(0, inf ^ 1, p + 2 * d);
      if (id2 == -1) {
        return {};
      }
      int p2 = id_pos[id2];
      int k = (p2 - p - 2 * d) / 2;
      assert(k >= 0);
      assert(p % 2 == p2 % 2);
      return {d + k, id, id2};
    } else {
      // p - d - k = p2 + d + k
      // e simetric
      // p2 + 2k = p - 2d
      // p2 tre sa fie mai mic decat p-2d
      int id2 = smaller_pos(1, inf ^ 1, p - 2 * d);
      if (id2 == -1) {
        return {};
      }
      int p2 = id_pos[id2];
      int k = (p - p2 - 2 * d) / 2; // sper
      assert(k >= 0);
      assert(p % 2 == p2 % 2);
      return {d + k, id, id2};
    }
  }
  
  Meet infect(int d, int id) {
    if (!is_active[id] || when_infected[id] != INF) {
      return {};
    }
    when_infected[id] = d;
    int dir = id_dir[id], p = id_pos[id];
    
    // cerr << "INFECT " << d << " | " << id << endl;
    
    // tre sa dau purge la alea cu aceeasi directie
    // da ig pot doar sa gen
    // gen e ok gen
    while (true) {
      int idx = exact_pos(dir, 0, p);
      if (idx == -1) {
        break;
      }
      when_infected[idx] = d;
      pos[dir][0].erase({id_pos[idx], idx});
      pos[dir][1].insert({id_pos[idx], idx});
    }
    
    return find_meet(d, id);
  }
  
  // returneaza {id, prima intalnire care il contine pe asta}
  pair<int, Meet> add(int d, int s, int t, int is_inf) {
    ++max_id;
    int id = max_id;

    // cerr << "ADD " << d << " " << s << " " << t << " | " << id << endl;
    
    is_active.pb(true);
    when_infected.pb(INF);
    id_dir.pb(s <= t);
    if (id_dir[id]) {
      id_pos.pb(s - d);
    } else {
      id_pos.pb(s + d);
    }
    pos[id_dir[id]][0].insert({id_pos[id], id});
    
    if (is_inf || exact_pos(id_dir[id], 1, id_pos[id]) != -1) {
      return {id, infect(d, id)};
    }
    
    return {id, find_meet(d, id)};
  }
  
  Meet remove(int d, int id) {
    // cerr << "REM " << d << " | " << id << endl;
    
    int dir = id_dir[id], p = id_pos[id], inf = (when_infected[id] != INF);
    pos[dir][inf].erase({p, id});
    
    Meet temp = find_meet(d, id);
    is_active[id] = false;
    if (temp.d == INF) {
      return {};
    }
    return find_meet(d, temp.id2);
  }
  
  Meet meet(Meet M) {
    auto [d, id1, id2] = M;
    if (!is_active[id1] || !is_active[id2]) {
      return {};
    }
    
    if (when_infected[id2] != INF) {
      swap(id1, id2);
    }
    if (when_infected[id2] != INF) {
      return {};
    }

    // cerr << "MEET " << d << " | " << id1 << " " << id2 << endl;
    
    infect(d, id2);
    return min(find_meet(d, id1), find_meet(d, id2));
  }
};

struct Event {
  int tip, par, d, x, y, z;
  bool operator<(const Event& b) const {
    if (d == b.d) {
      if (tip == b.tip) {
        return array<int, 4>{par, x, y, z} < array<int, 4>{b.par, b.x, b.y, b.z};
      }
      return tip < b.tip;
    }
    return d < b.d;
  }
};

const int EVENT_REM = 0, EVENT_ADD = 1, EVENT_MEET = 2;

vector<int32_t> solve(vector<pair<int32_t, int32_t>> R, vector<long long> D, vector<int32_t> S, vector<int32_t> T, vector<bool> I) {
  int n = R.size() + 1, m = D.size();
  
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[R[i].first].pb(R[i].second);
    adj[R[i].second].pb(R[i].first);
  }
  
  vector<int> parity(m);
  for (int i = 0; i < m; ++i) {
    parity[i] = (S[i] + D[i]) % 2;
  }
  
  // rezolv vector intai
  set<Event> events;
  for (int i = 0; i < m; ++i) {
    events.insert({EVENT_ADD, parity[i], D[i], i, 0, 0});
  }
  
  vector<int> id(m);
  array<Arbore, 2> chestie{};
  while (!events.empty()) {
    Event e = *events.begin();
    events.erase(events.begin());
    // cerr << "!!! " << e.par << endl;
    
    Meet meet{};
    if (e.tip == EVENT_ADD) {
      int i = e.x;
      auto ret = chestie[e.par].add(e.d, S[i], T[i], I[i]);
      id[i] = ret.first;
      meet = ret.second;
      events.insert(Event{EVENT_REM, e.par, e.d + abs(S[i] - T[i]) + 1, id[i], 0, 0});
    } else if (e.tip == EVENT_REM) {
      meet = chestie[e.par].remove(e.d, e.x);
    } else {
      meet = chestie[e.par].meet({e.d, e.x, e.y});
    }
    
    if (meet.d != INF) {
      // cerr << "FOUND MEETING " << meet.d << " | " << meet.id1 << " " << meet.id2 << endl;
      events.insert(Event{EVENT_MEET, e.par, meet.d, meet.id1, meet.id2, 0});
    }
  }
  
  vector<int32_t> ans(m);
  for (int i = 0; i < m; ++i) {
    int wi = chestie[parity[i]].when_infected[id[i]];
    if (wi == INF) {
      ans[i] = 0;
    } else {
      ans[i] = (D[i] + abs(S[i] - T[i])) - wi + 1;
    }
  }
  
  return ans;
  
  // vector<int> sz(n);
  // auto dfs = [&](auto&& self, int u) -> void {
    // sz[u] = 1;
    // for (int v : adj[u]) {
      // self(self, v);
      // sz[u] += sz[v];
    // }
  // };
  // dfs(dfs, 0);
}
