#include <bits/stdc++.h>
#include "infection.h"
#define MAXN 150000
#define LOG 20
#define fi first
#define se second
using namespace std;
long long t[MAXN], tt[MAXN][LOG], n;
vector<pair<long long, pair<long long, long long>>> meet;
long long inf[MAXN], x[MAXN], lvl[MAXN];
vector<long long>vec[MAXN];
vector<int>ans;
void dfs(int nod, int tata) {
    t[nod]=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=0; i<n; i++) {
        tt[i][0]=t[i];
    }
    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];
        }
    }
}
bool is_ancestor(int x, int y) {
    int i;
    int dist=lvl[y]-lvl[x];
    for (i=0; i<LOG; i++) {
        if ((1<<i)>dist) break;
        if (((1<<i)&dist)!=0) {
            dist-=(1<<i);
            y=tt[y][i];
        }
    }
    return (x==y);
}
int lca(int x, int y) {
    int i;
    if (lvl[x]>lvl[y]) swap(x, y);
    if (is_ancestor(x, y)==1) return x;
    if (lvl[x]!=lvl[y]) {
        int dist=lvl[y]-lvl[x];
        for (i=0; i<LOG; i++) {
            if ((1<<i)>dist) break;
            if (((1<<i)&dist)!=0) {
                dist-=(1<<i);
                y=tt[y][i];
            }
        }
    }
    for (i=LOG-1; i>=0; i--) {
        if (tt[x][i]!=tt[y][i]) {
            x=tt[x][i];
            y=tt[y][i];
        }
    }
    return t[x];
}
vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    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);
    int i, j;
    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++) {
            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]) {
                meet.push_back({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]]) meet.push_back({D[j]+lvl[S[j]]-lvl[x[j]], {i, j}});
                else meet.push_back({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) {
                int dist1=D[i]+lvl[S[i]]-lvl[z]-(D[j]+lvl[S[j]]-lvl[x[j]]+lvl[z]-lvl[x[j]]);
                int 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) {
                    meet.push_back({D[i]+lvl[S[i]]-lvl[z], {i, j}});
                }
                if (dist2==0) {
                    if (lvl[x[i]]<lvl[x[j]]) {
                        meet.push_back({D[i]+lvl[S[i]]-lvl[x[j]], {i, j}});
                    }
                    else {
                        meet.push_back({D[i]+lvl[S[i]]-lvl[x[i]], {i, j}});
                    }
                }
                if (dist1*dist2<0 && dist1%2==0) {
                    meet.push_back({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) {
                int dist1=D[j]+lvl[S[j]]-lvl[z]-(D[i]+lvl[S[i]]-lvl[x[i]]+lvl[z]-lvl[x[i]]);
                int 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) {
                    meet.push_back({D[j]+lvl[S[j]]-lvl[z], {i, j}});
                }
                if (dist2==0) {
                    if (lvl[x[j]]<lvl[x[i]]) {
                        meet.push_back({D[j]+lvl[S[j]]-lvl[x[i]], {i, j}});
                    }
                    else {
                        meet.push_back({D[j]+lvl[S[j]]-lvl[x[j]], {i, j}});
                    }
                }
                if (dist1*dist2<0 && dist1%2==0) {
                    meet.push_back({D[j]+lvl[S[j]]-lvl[z]-dist1/2, {i, j}});
                }
            }
        }
    }
    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;
    }
    for (auto x:meet) {
        //cout<<x.fi<<' '<<x.se.fi<<' '<<x.se.se<<'\n';
        if (I[x.se.fi]==0 && I[x.se.se]==0) {
            continue;
        }
        if (I[x.se.fi]==1 && I[x.se.se]==1) {
            continue;
        }
        if (I[x.se.fi]==0) swap(x.se.fi, x.se.se);
        inf[x.se.se]=x.fi;
        I[x.se.se]=1;
    }
    ans.resize(m);
    for (i=0; i<m; i++) {
        ans[i]=lvl[S[i]]-lvl[x[i]]+lvl[T[i]]-lvl[x[i]]+1-(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
*/
