#include "infection.h"
#include <bits/stdc++.h>
#define out(x) #x<<" = "<<x<<" "
using namespace std;

const int MAX = 2 * 1e5 + 10;
int head[MAX], pos[MAX], heavy[MAX], dep[MAX], sz[MAX], par[MAX], n;
int sp[18][MAX];
vector<int> r[MAX];

void dfs(int x, int p){
    sz[x] = 1;
    heavy[x] = -1;
    par[x] = p;
    dep[x] = dep[p] + 1;

    for(int i: r[x]){
        if(i == p) continue;
        dfs(i, x);
        sz[x] += sz[i];
        if(heavy[x] == -1 || sz[i] > sz[heavy[x]]) heavy[x] = i;
    }
}

int curr;
void heavy_light(int x, int par, int h){
    pos[x] = ++curr;
    head[x] = h;
    if(heavy[x] == -1) return;
    heavy_light(heavy[x], x, h);
    for(int i: r[x]){
        if(i == par || i == heavy[x]) continue;
        heavy_light(i, x, i);
    }
}

void sp_table(){
    for(int i = 1; i < n; i++){
        sp[0][i] = par[i];
    }

    for(int i = 1; i <= 17; i++){
        for(int j = 1; j < n; j++){
            if(dep[j] <= (1 << i)) continue;
            sp[i][j] = sp[i - 1][sp[i - 1][j]];
        }
    }
}

int find_lca(int x, int y){
    if(dep[x] < dep[y])swap(x, y);
    for(int i = 17; i >= 0; i--){
        if(dep[x] <= (1 <<i)) continue;
        if(dep[sp[i][x]] > dep[y]) continue;
        x = sp[i][x];
    }

    for(int i = 17; i>= 0; i--){
        if(dep[x] <= (1<<i)) continue;
        if(sp[i][x] == sp[i][y]) continue;
        x = sp[i][x];
        y = sp[i][y];
    }
    return par[x];
}



set<long long> t[2][4 * MAX];
vector<long long> lazy[2][4 * MAX];

void push_lazy(int x, int l, int r, bool flag){
    if(lazy[flag][x].size() == 0) return;
    int mid = (l + r)/2;

    for(int i: lazy[flag][x]){
        if(flag){
            t[flag][2 * x].insert(i + r - mid);
            t[flag][2 * x + 1].insert(i);
            lazy[flag][2 * x].push_back(i + r - mid);
            lazy[flag][2 * x + 1].push_back(i);
            continue;
        }
        t[flag][2 * x].insert(i);
        t[flag][2 * x + 1].insert(i + mid - l + 1);

        lazy[flag][2 * x].push_back(i);
        lazy[flag][2 * x + 1].push_back(i + mid - l + 1);
    }
    lazy[flag][x].clear();
}

void update(int x, int l, int r, int ll, int rr, long long d, bool flag){
    if(ll > rr) return;
    if(l == ll && rr == r){
        lazy[flag][x].push_back(d);
        t[flag][x].insert(d);
        return;
    }
    int mid = (l + r)/2;
    update(x * 2, l, mid, ll, min(rr, mid), (!flag)? d: (r - mid + d), flag);
    update(x * 2 + 1, mid + 1, r, max(mid + 1, ll) , rr, (flag)? d: (mid - l + 1 + d), flag);
}

long long query(int x, int l, int r, int ll, int rr, long long d, bool flag){
    if(ll > rr) return 1e16;
    if(l == ll && rr == r){
        auto curr = t[flag][x].find(d);
        if(curr != t[flag][x].end()) return d;
        return 1e16;
    }
    push_lazy(x, l, r, flag);
    int mid = (l + r)/2;
    return min(query(x * 2, l, mid, ll, min(rr, mid), (!flag)? d: (r - mid + d), flag), query(x * 2 + 1, mid + 1, r, max(mid + 1, ll) , rr, (flag)? d: (mid - l + 1 + d), flag));
}

vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    for(int i = 0; i < R.size(); i++){
        r[R[i].first].push_back(R[i].second);
        r[R[i].second].push_back(R[i].first);
        n = max(n, R[i].first);
        n = max(n, R[i].second);
    }
    n ++;
    dfs(0, 0);
    sp_table();

    vector<int> ans;
    for(int i = 0; i < I.size(); i++){
        ans.push_back(0);
        if(!I[i]) continue;

        int l = find_lca(S[i], T[i]);
        int a = S[i], b = T[i];
        //cout<<out(l)<<out(dep[a])<<out(dep[b])<<out(dep[l])<<endl;
        while(head[a] != head[l]){
            update(1, 0, n - 1, pos[head[a]], pos[a], D[i] + dep[S[i]] - dep[a], 1);
            a = par[head[a]];
        }

        if(a != l) update(1, 0, n - 1, pos[l], pos[a], D[i] + dep[S[i]] - dep[a], 1);

        while(head[b] != head[l]){
            update(1, 0, n - 1, pos[head[b]], pos[b], D[i] + dep[S[i]] - dep[l] + dep[b] - dep[l], 0);
            b = par[head[b]];
        }

        if(b != l || a == l) update(1, 0, n - 1, pos[l], pos[b], D[i] + dep[l] + dep[b] - dep[l], 0);

        ans[i] = dep[a] + dep[b] - 2  * dep[l] + 1;
    }

    for(int i = 0; i < I.size(); i++){
        //ans.push_back(0);
        if(I[i]) continue;

        int l = find_lca(S[i], T[i]);
        int a = S[i], b = T[i];
        long long x = D[i] + dep[a] + dep[b] - 2 * dep[l] + 1;
        while(head[a] != head[l]){
            x = min (x, query(1, 0, n - 1, pos[head[a]], pos[a], D[i] + dep[S[i]] - dep[a], 1));
            a = par[head[a]];
        }

        if(a != l) x = min(x, query(1, 0, n - 1, pos[l], pos[a], D[i] + dep[S[i]] - dep[a], 1));

        while(head[b] != head[l]){
            x = min(x, query(1, 0, n - 1, pos[head[b]], pos[b], D[i] + dep[S[i]] - dep[l] + dep[b] - dep[l], 0));
            b = par[head[b]];
        }

        if(b != l || a == l) x = min(x, query(1, 0, n - 1, pos[l], pos[b], D[i] + dep[l] + dep[b] - dep[l], 0));

        ans[i] = (D[i] + dep[a] + dep[b] - 2 * dep[l] + 1) - x;
    }


    return ans;
}
