#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
#define int long long
const int NMAX = 150000;
const int LOGMAX = 17;
#define ll long long
vector<pair<int, int>> r;
vector<ll> d;
vector<int> s;
vector<int> t;
vector<bool> inf;
vector<int> v[NMAX + 5];
int bl[NMAX + 5][LOGMAX + 1];
int timp = 0;
int in[NMAX + 5], out[NMAX + 5];
int depth[NMAX + 5];
void dfsini(int nod, int par)
{
    bl[nod][0] = par;
    for(int i = 1; i <= LOGMAX; i++)
        bl[nod][i] = bl[bl[nod][i - 1]][i - 1];
    in[nod] = ++timp;
    for(auto it : v[nod])
    if(it != par)
    {
        depth[it] = depth[nod] + 1;
        dfsini(it, nod);
    }
    out[nod] = ++timp;
}
bool isAncestor(int x, int y)
{
    return (in[x] <= in[y] && out[x] >= out[y]);
}
int lca(int x, int y)
{
    if(isAncestor(x, y)) return x;
    if(isAncestor(y, x)) return y;
    for(int i = LOGMAX; i >= 0; i--)
        if(!isAncestor(bl[x][i], y))
            x = bl[x][i];
    return bl[x][0];
}
vector<int> path[NMAX + 5];
vector<int> getPath(int x, int y)
{
    vector<int> pth;
    int lc = lca(x, y);
    int nod = x;
    while(nod != lc)
    {
        pth.push_back(nod);
        nod = bl[nod][0];
    }
    vector<int> pth2;
    nod = y;
    while(nod != lc)
    {
        pth2.push_back(nod);
        nod = bl[nod][0];
    }
    reverse(pth2.begin(), pth2.end());
    pth.push_back(lc);
    for(auto it : pth2)
        pth.push_back(it);
    return pth;
}
int pathlen(int x, int y)
{
    int lc = lca(x, y);
    return (depth[x] - depth[lc] + depth[y] - depth[lc] + 1);
}
int where[NMAX + 5];
int cntinf[NMAX + 5];
int ant[NMAX + 5];
ll mininf[NMAX + 5];
set<pair<pair<ll, int>, int>> st;
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
)
{
    r = R, d = D, s = S, t = T, inf = I;
    for(int i = 0; i < r.size(); i++)
    {
        v[r[i].first].push_back(r[i].second);
        v[r[i].second].push_back(r[i].first);
    }
    depth[0] = 1;
    dfsini(0, 0);
    vector<int> rsp;
    for(int i = 0; i < d.size(); i++)
        path[i] = getPath(s[i], t[i]);
    for(int i = 0; i < d.size(); i++)
        st.insert({{d[i], 1 - inf[i]}, i}), where[i] = 0, mininf[i] = (inf[i] ? d[i] : -1);
    while(!st.empty())
    {
        auto it = (*st.begin());
        st.erase(st.begin());
        ll sec = it.first.first;
        bool infect = 1 - it.first.second;
        int ind = it.second;
        if(infect)
            cntinf[ant[ind]]--;
        if(where[ind] >= path[ind].size())
            continue;
        int nod = path[ind][where[ind]];
        if(cntinf[nod] > 0)
            infect = 1;
        if(infect)
            cntinf[nod]++;
        if(infect && mininf[ind] == -1)
            mininf[ind] = sec;
        where[ind]++;
        st.insert({{sec + 1, 1 - infect}, ind});
        ant[ind] = nod;
    }
    vector<int> rez;
    for(int i = 0; i < d.size(); i++)
    {
        //el devine infectat la secunda mininf[i].
        if(mininf[i] == -1)
            rez.push_back(0);
        else
            rez.push_back(pathlen(s[i], t[i]) - (mininf[i] - d[i]));
    }
    return rez;
}
