#include <bits/stdc++.h>
#include "infection.h"
#define MAXN 5005
#define LOG 20
#define fi first
#define se second
#pragma GCC optimize ("Ofast", "unroll-loops")
#pragma GCC target ("avx2")
using namespace std;
int tt[MAXN][LOG+5], n, poww2[LOG+5];
vector<pair<long long, pair<int, int>>> meet;
set<pair<long long, pair<int, int>>> meet1, nullvector;
long long inf[MAXN];
int x[MAXN], lvl[MAXN];
vector<int>vec[MAXN];
vector<int>ans;
void dfs(int nod, int tata) {
    tt[nod][0]=tata;
    for (auto x:vec[nod]) {
        if (x==tata) continue;
        lvl[x]=lvl[nod]+1;
        dfs(x, nod);
    }
}
void binary_lifting(int n) {
    int i, j;
    for (i=1; i<LOG; i++) {
        for (j=0; j<n; j++) {
            if (tt[j][i-1]==-1) tt[j][i]=-1;
            else tt[j][i]=tt[tt[j][i-1]][i-1];
        }
    }
}
int lca(int x, int y) {
    int i;
    if (lvl[x]>lvl[y]) swap(x, y);
    if (lvl[x]!=lvl[y]) {
        int dist=lvl[y]-lvl[x];
        for (i=0; i<LOG; i++) {
            if (poww2[i]>dist) break;
            if ((poww2[i]&dist)!=0) {
                dist-=poww2[i];
                y=tt[y][i];
            }
        }
    }
    if (x==y) return x;
    for (i=LOG-1; i>=0; i--) {
        if (tt[x][i]<1) continue;
        if (tt[x][i]!=tt[y][i]) {
            x=tt[x][i];
            y=tt[y][i];
        }
    }
    return tt[x][0];
}
bool is_ancestor(int x, int y) {
    return (x==lca(x, y));
}
vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    int i, j;
    poww2[0]=1;
    for (i=1; i<LOG; i++) {
        poww2[i]=poww2[i-1]*2;
    }
    for (auto x:R) {
        vec[x.fi].push_back(x.se);
        vec[x.se].push_back(x.fi);
    }
    lvl[0]=1;
    dfs(0, -1);
    binary_lifting(R.size()+1);
    n=R.size()+1;
    int m=I.size();
    for (i=0; i<m; i++) {
        x[i]=lca(S[i], T[i]);
    }
    for (i=0; i<m; i++) {
        for (j=i+1; j<m; j++) {
            meet1=nullvector;
            int z=lca(S[i], S[j]);
            if (is_ancestor(x[i], z)==1 && is_ancestor(x[j], z)==1 && lvl[S[i]]+D[i]==lvl[S[j]]+D[j]) {
                meet1.insert({D[i]+lvl[S[i]]-lvl[z], {i, j}});
            }
            z=lca(T[j], T[i]);
            if (is_ancestor(x[i], z)==1 && is_ancestor(x[j], z)==1 && D[j]+lvl[S[j]]-lvl[x[j]]+lvl[z]-lvl[x[j]]==D[i]+lvl[S[i]]-lvl[x[i]]+lvl[z]-lvl[x[i]]) {
                if (lvl[x[i]]<lvl[x[j]]) meet1.insert({D[j]+lvl[S[j]]-lvl[x[j]], {i, j}});
                else meet1.insert({D[i]+lvl[S[i]]-lvl[x[i]], {i, j}});
            }
            z=lca(S[i], T[j]);
            if (is_ancestor(x[i], z)==1 && is_ancestor(x[j], z)==1) {
                long long dist1=D[i]+lvl[S[i]]-lvl[z]-(D[j]+lvl[S[j]]-lvl[x[j]]+lvl[z]-lvl[x[j]]);
                long long dist2;
                if (lvl[x[i]]<lvl[x[j]]) {
                    dist2=D[i]+lvl[S[i]]-lvl[x[j]]-(D[j]+lvl[S[j]]-lvl[x[j]]);
                }
                else {
                    dist2=D[i]+lvl[S[i]]-lvl[x[i]]-(D[j]+lvl[S[j]]-lvl[x[j]]+lvl[x[i]]-lvl[x[j]]);
                }
                if (dist1==0) {
                    meet1.insert({D[i]+lvl[S[i]]-lvl[z], {i, j}});
                }
                if (dist2==0) {
                    if (lvl[x[i]]<lvl[x[j]]) {
                        meet1.insert({D[i]+lvl[S[i]]-lvl[x[j]], {i, j}});
                    }
                    else {
                        meet1.insert({D[i]+lvl[S[i]]-lvl[x[i]], {i, j}});
                    }
                }
                if (dist1*dist2<0 && dist1%2==0) {
                    meet1.insert({D[i]+lvl[S[i]]-lvl[z]-dist1/2, {i, j}});
                }
            }
            z=lca(S[j], T[i]);
            if (is_ancestor(x[j], z)==1 && is_ancestor(x[i], z)==1) {
                long long dist1=D[j]+lvl[S[j]]-lvl[z]-(D[i]+lvl[S[i]]-lvl[x[i]]+lvl[z]-lvl[x[i]]);
                long long dist2;
                if (lvl[x[j]]<lvl[x[i]]) {
                    dist2=D[j]+lvl[S[j]]-lvl[x[i]]-(D[i]+lvl[S[i]]-lvl[x[i]]);
                }
                else {
                    dist2=D[j]+lvl[S[j]]-lvl[x[j]]-(D[i]+lvl[S[i]]-lvl[x[i]]+lvl[x[j]]-lvl[x[i]]);
                }
                if (dist1==0) {
                    meet1.insert({D[j]+lvl[S[j]]-lvl[z], {i, j}});
                }
                if (dist2==0) {
                    if (lvl[x[j]]<lvl[x[i]]) {
                        meet1.insert({D[j]+lvl[S[j]]-lvl[x[i]], {i, j}});
                    }
                    else {
                        meet1.insert({D[j]+lvl[S[j]]-lvl[x[j]], {i, j}});
                    }
                }
                if (dist1*dist2<0 && dist1%2==0) {
                    meet1.insert({D[j]+lvl[S[j]]-lvl[z]-dist1/2, {i, j}});
                }
            }
            if (meet1.empty()) continue;
            for (auto x:meet1) {
                meet.push_back(x);
            }
        }
    }
    for (i=0; i<m; i++) {
        if (I[i]==1) inf[i]=D[i];
        else inf[i]=lvl[S[i]]-lvl[x[i]]+lvl[T[i]]-lvl[x[i]]+D[i]+1;
    }
    sort(meet.begin(), meet.end());
    for (auto x:meet) {
        //cout<<x.fi<<' '<<x.se.fi<<' '<<x.se.se<<'\n';
        if (I[x.se.fi]==I[x.se.se]) {
            continue;
        }
        if (I[x.se.fi]==0) inf[x.se.fi]=x.fi, I[x.se.fi]=1;
        else inf[x.se.se]=x.fi, I[x.se.se]=1;
    }
    ans.resize(m);
    for (i=0; i<m; i++) {
        ans[i]=int((lvl[S[i]]-lvl[x[i]]+lvl[T[i]]-lvl[x[i]]+1)*1ll-(inf[i]-D[i]));
        //ans[i]=lvl[S[i]]-lvl[x[i]]+lvl[T[i]]-lvl[x[i]];
    }
    return ans;
}

/*
6 4
0 1
0 2
0 3
0 4
0 5
1 3 4 0
3 3 5 1
3 2 5 0
1 3 4 1
*/
