#include "infection.h"
#include <vector>
#include <utility>
#include <array>
#include <cstdint>
#include <cmath>
#include <bitset>
#include <iostream>
#define int long long
using namespace std;
const int MAXN = 2e5+5;
const int LOG = 20;
const int inf = 1e18;


int n, m;
vector<int> g[MAXN];
int d[MAXN];
int up[MAXN][LOG];
int bg[MAXN], en[MAXN];
array<int,2> tm[MAXN];
int tinf[MAXN];
bitset<MAXN> v1, v2;

void dfs(int x, int p){
    for(int i = 1; i < LOG; ++i){
        up[x][i] = up[up[x][i-1]][i-1];
    }
    for(int k : g[x]){
        if(k==p) continue;
        up[k][0] = x;
        d[k] = d[x]+1;
        dfs(k,x);
    }
}

int lift(int x, int k){
    for(int i = LOG-1; i >= 0; --i){
        if((1<<i) <= k){
            x = up[x][i];
            k -= (1<<i);
        }
    }
    return x;
}
int lca(int x, int y){
    if(d[x] < d[y]) swap(x,y);
    x = lift(x,d[x]-d[y]);
    if(x == y) return x;
    for(int i = LOG-1; i >= 0; --i){
        if(up[x][i] != up[y][i]){
            x = up[x][i], y = up[y][i];
        }
    }
    return up[x][0];
}
int dist(int x, int y){
    int z = lca(x, y);
    return d[x] + d[y] - 2*d[z];
}

int advance(int p, int k){
    int x = bg[p], y = en[p];
    int z = lca(x,y);
    //cout << "gsigs " << x << ' ' << y << ' ' << k << ' ' << d[x]+d[y]-2*d[z] << '\n';
    if(d[x]-d[z] >= k) return lift(x,k);
    else if(k <= d[x]+d[y]-2*d[z]) return lift(y,d[x]+d[y]-2*d[z]-k);
    else return -1;
}

int check(int x, int y){
    if(tm[x][0] > tm[y][0]) swap(x,y);
    int p1 = advance(x,tm[y][0]-tm[x][0]), p2 = bg[y];
    if(p1 == -1) return 0;
    int k = dist(p1,p2);
    if(k%2) return 0;
    k /= 2;
    int tmp = advance(y,k);
    if(advance(x,k+tm[y][0]-tm[x][0]) != tmp || tmp == -1) return 0;
    bool upx, upy;
    upx = upy = 0;
    if(tinf[x] <= tm[y][0]+k) upy = 1;
    if(tinf[y] <= tm[y][0]+k) upx = 1;
    if(upx) tinf[x] = min(tinf[x], tm[y][0]+k);
    if(upy) tinf[y] = min(tinf[y], tm[y][0]+k);
    //cout << x << ' ' << y << ' ' << k << ' ' << tmp << ' ' << tm[y][0]-tm[x][0] << '\n';
    return 1;
}

std::vector<int32_t> solve(
    std::vector<std::pair<int32_t, int32_t>> R,
    std::vector<long long> D,
    std::vector<int32_t> S,
    std::vector<int32_t> T,
    std::vector<bool> I
){
    n = R.size()+1;
    m = D.size();
    if(n > 5005 || m > 5005) return {};
    for(auto [x,y] : R){
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0,0);
    vector<int> q;
    fill(tinf,tinf+m,inf);
    for(int i = 0; i < m; ++i){
        bg[i] = S[i], en[i] = T[i];
        tm[i][0] = D[i], tm[i][1] = D[i] + dist(bg[i], en[i]);
        if(I[i]){
            v1[i] = v2[i] = 1;
            tinf[i] = tm[i][0];
            q.push_back(i);
        }
        //cout << "i: " << i << ' ' << tm[i][0] << ' ' << tm[i][1] << '\n';
    }
    while(!q.empty()){
        vector<int> v;
        for(int i = 0; i < m; ++i){
            if(v1[i] == 0) v.push_back(i);
        }
        //cout << "q: "; for(int k : q) cout << ' ' << k; cout << '\n';
        //cout << "v: "; for(int k : v) cout << ' ' << k; cout << '\n';
        for(int k : q){
            for(int x : v){
                if(check(k,x)) v1[x] = 1;
            }
        }
        q.clear();
        int idx = -1;
        for(int x : v){
            if(v1[x]){
                if(idx == -1) idx = x;
                else if(tinf[x] < tinf[idx]) idx = x;
                v1[x] = 0;
            }
        }
        if(idx == -1) break;
        q = {idx};
        v1[idx] = 1;
    }
    vector<int32_t> ans(m,0);
    for(int i = 0; i < m; ++i){
        ans[i] = max(0ll,tm[i][1]-tinf[i]+1);
        //cout << tinf[i] << '\n';
    }
    return ans;
}
