#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair <int, int>
#define ld long double
#define ins insert
#define pb push_back
using namespace std;

const int N = 2e5 + 5;
const ll inf = 1e13;

vector <int> g[N];
int pr[N], tin[N], tout[N];
int timer;
int up[N][30];
void dfs(int v, int p = 0)
{
    timer++;
    tin[v] = timer;
    pr[v] = p;
    up[v][0] = p;
    for (int i = 1; i < 30; i++) up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto to: g[v]) if (to != p)
    {
        dfs(to, v);
    }
    timer++;
    tout[v] = timer;
}

deque <int> way[N];

bool upper(int v, int u)
{
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

ll dl[N];

ll lca(int v, int u)
{
    ll ans = 0;
    for (int i = 29; i >= 0; i--) if (!upper(up[v][i], u))
    {
        ans += (1ll << i);
        v = up[v][i];
    }
    for (int i = 29; i >= 0; i--) if (!upper(up[u][i], v))
    {
        ans += (1ll << i);
        u = up[u][i];
    }
    if (v != u) ans++;
    return ans;
}

ll lst[N];
ll whn[N];
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
)
{
    int n = R.size() + 1, m = D.size();
    for (auto to: R) {g[to.F + 1].pb(to.S + 1); g[to.S + 1].pb(to.F + 1);}
    dfs(1);
    for (int i = 1; i <= m; i++)
    {
        whn[i] = (I[i - 1] ? 0 : inf);
        dl[i] = lca(S[i - 1], T[i - 1]);
    }
    vector <int> ans;
    for (int i = 1; i <= m; i++)
    {
        ans.pb(max(0ll, min(dl[i] + D[i - 1] - whn[i], dl[i])));
    }
    return ans;
}


//int32_t main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector <pii> r;
//    vector <int> s, t;
//    vector <bool> ii;
//    vector <ll> d;
//    for (int i = 1; i < n; i++)
//    {
//        int v, u;
//        cin >> v >> u;
//        r.pb({v, u});
//    }
//    for (int i = 1; i <= m; i++)
//    {
//        int D, S, T, I;
//        cin >> D >> S >> T >> I;
//        d.pb(D);
//        s.pb(S);
//        t.pb(T);
//        ii.pb(I);
//    }
//    vector <int> ans = solve(r, d,s,t,ii);
//    for (auto to: ans) cout << to << endl;
//    return 0;
//}
