#include<bits/stdc++.h>
#include "infection.h"
#define X first
#define Y second
using namespace std;
const long long maxn=5e3+10;
int n,m;
vector<long long> v[maxn];
long long d[maxn],s[maxn],t[maxn];
long long dp[maxn],bin[maxn][15],dis[maxn],id[maxn];
bool inf[maxn];
void dfs(long long i,long long par)
{
    dp[i]=dp[par]+1;
    bin[i][0]=par;
    if(i==0)
    {
        bin[i][0]=-1;
    }
    for(auto nb:v[i])
    {
        if(nb==par)
        {
            continue;
        }
        dfs(nb,i);
    }
}
void build()
{
    for(long long j=1; j<=13; j++)
    {
        for(long long i=0; i<m; i++)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
        }
    }
}
map<long long,vector<long long>> mp[maxn];
long long up(long long x,long long i)
{
    for(long long j=13; j>=0; j--)
    {
        if(i&(1<<j))
        {
            x=bin[x][j];
        }
    }
    return x;
}
long long LCA(long long x,long long y)
{
    if(dp[x]>dp[y])
    {
        swap(x,y);
    }
    y=up(y,dp[y]-dp[x]);
    if(x==y)
    {
        return x;
    }
    for(long long j=13; j>=0; j--)
    {
        if(bin[x][j]!=bin[y][j])
        {
            x=bin[x][j];
            y=bin[y][j];
        }
    }
    return bin[x][0];
}
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)
{
    m=D.size();
    n=0;
    for(auto i:R)
    {
        v[i.X].push_back(i.Y);
        v[i.Y].push_back(i.X);
        n=max(n,i.X);
        n=max(n,i.Y);
    }
    n++;
    for(long long i=0; i<m; i++)
    {
        d[i]=D[i];
        s[i]=S[i];
        t[i]=T[i];
        inf[i]=I[i];
        id[i]=1e18;
        if(inf[i]==1)
        {
            id[i]=d[i];
        }
    }
    dp[0]=-1;
    dfs(0,0);
    build();
    for(long long i=0; i<m; i++)
    {
        long long lca=LCA(s[i],t[i]);
        long long r=dp[s[i]]+dp[t[i]]-2*dp[lca];
        dis[i]=r;
        long long nb=s[i];
        mp[nb][d[i]].push_back(i);
        long long br=0;
        nb=bin[nb][0];
        while(nb!=lca&&nb!=-1)
        {
            br++;
            mp[nb][d[i]+br].push_back(i);
            nb=bin[nb][0];
        }
        if(nb!=-1)
        {
            mp[nb][d[i]+br+1].push_back(i);
        }
        nb=t[i];
        br=d[i]+r;
        mp[nb][br].push_back(i);
        nb=bin[nb][0];
        while(nb!=lca&&nb!=-1)
        {
            br--;
            mp[nb][br].push_back(i);
            nb=bin[nb][0];
        }
        if(nb!=-1)
        {
            mp[nb][br-1].push_back(i);
        }
    }
    for(long long i=0; i<n; i++)
    {
        for(auto [key,value]:mp[i])
        {
            bool lamp=0;
            int br=0;
            for(auto z:value)
            {
                if(inf[z]==1)
                {
                    lamp=1;
                    br++;
                }
            }
            if(lamp==1)
            {
                for(auto z:value)
                {
                    if(inf[z]==1)
                    {
                        if(br>1)
                        {
                            id[z]=min(id[z],key);
                        }
                    }
                    else
                    {
                        inf[z]=1;
                        id[z]=min(id[z],key);
                    }
                }
            }
        }
    }
    vector<int> ans;
    for(long long i=0; i<m; i++)
    {
        if(id[i]==1e18)
        {
            ans.push_back(0);
            continue;
        }
        ans.push_back(d[i]+dis[i]-id[i]+1);
    }
    return ans;
}

