1162_Min_Max_Roads.md

Algorithm: Segment Tree

Problem: 1162 Min Max Roads

#include <bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define ll long long
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define vb vector<bool>
#define vs vector<string>
///............x...........///
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define ff first
#define ss second
#define bg begin()
#define UNIQUE(X) (X).erase(unique(all(X)), (X).end())
#define ft cout << "for test"<<endl;
#define read(v, a, n) for (int i = a; i<n; i++)cin>>v[i];
#define print(v) for (auto it : v)cout << it<<" ";cout << endl;
#define PI acos(-1.0)
#define yes cout <<"Yes"<< endl
#define no cout<<"No"<<endl
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define t_c int test, cs = 1;cin>>test;while (test--)
#define casep cout<<"Case "<< cs++<<":\n";
///................function.....................///

#define D(a) (double)(a)
#define siz(s) (int)(s.size())
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define Min(a) *min_element(all(a))
//#define mod 1000000007
//........constant........///
const ll N = 1e6+5;
void file(){
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
}
struct node{
    int par,mn,mx;
};
const int Log=19;
class Lca{
    public:
    vector<vector<pii>> g;
    vector<vector<node>>up;
    vector<int> depth;
    int n;
    Lca(int _n){
        n = _n;
        up.resize(n+1,vector<node>(Log,{-1,N,0}));
        g.resize(n+1);
        depth.resize(n+1);
    }
    void readTree(int root=1){
        int a,b,c;
        for(int i=1; i<n; i++){
            cin>>a>>b>>c;
            // cout<<a<<" .... "<<b<<" "<<c<<endl;
            g[a].push_back({b,c});
            g[b].push_back({a,c});
        }
        dfs(root,root,0,0);
        cal_sparse_table();
    }
    void dfs(int nd, int par, int d, int c){
        depth[nd]=d,up[nd][0]={par,c,c};
        if(nd==par)up[nd][0]={par,N,0};
        // cout<<nd<<" "<<par<<" "<<c<<" "<<c<<endl;
        for(auto to:g[nd]){
            if(to.first==par)continue;
            dfs(to.first,nd,d+1,to.second);
        }
    }
    void cal_sparse_table(){
        // cout<<"----------------------------"<<endl;
        for(int i=1; i<Log; i++){
            for(int j=1; j<=n; j++){
                if(up[j][i-1].par!=-1)
                    up[j][i] = up[up[j][i-1].par][i-1];
                    up[j][i].mn = min(up[j][i-1].mn,up[j][i].mn);
                    up[j][i].mx = max(up[j][i-1].mx,up[j][i].mx);
                    // if(i<2)
                    //     cout<<j<<" len "<<pow(2,i)<<" par "<<up[j][i].par<<" "<<up[j][i].mn<<" "<<up[j][i].mx<<endl;
            }
        }
    }
    pii lca_query(int u, int v){
        if(depth[u] < depth[v]) swap(u,v);
        long long diff = depth[u] - depth[v];
        int mn=N,mx=0;
        for(long long i = 0; i < Log; i++) {
            if( (diff>>i)&1 ) {
                // cout<<u<<" intro "<<i<<" "<<up[u][i].par<<endl;
                mn = min(mn,up[u][i].mn);
                mx = max(mx,up[u][i].mx);
                u = up[u][i].par;
                // cout<<mn<<" "<<mx<<endl;
            }
        }
        if(u == v) return {mn,mx};
        for(long long i = Log-1; i >= 0; i--) {
            if(up[u][i].par != up[v][i].par) {
                    mn = min({mn,up[u][i].mn,up[v][i].mn});
                    mx = max({mx,up[u][i].mx,up[v][i].mx});
                    u = up[u][i].par;
                    v = up[v][i].par;
            }
        }
        // int ret = up[u][0].par;
        mn = min({mn,up[u][0].mn,up[v][0].mn});
        mx = max({mx,up[u][0].mx,up[v][0].mx});
        return {mn,mx};
    }
//    int x_thParent(int u, int x){
//        for(long long i = 0; i < Log; i++) if( (x>>i)&1 ) u = up[u][i];
//        return u;
//    }
//    int cal_dis(int a, int b, int l){
//        return depth[a]+depth[b] - depth[l]*2;
//    }
};
int main(){
    FIO;
    // file();
    t_c{
        int n,i,j;
        cin>>n;
        Lca obj(n);
        obj.readTree();
        int m;
        cin>>m;
        casep;
        while(m--){
            int a,b;
            cin>>a>>b;
            pii ret = obj.lca_query(a,b);
            if(ret.first==N)ret.first=0;
            if(ret.second==N)ret.second=0;
            cout<<ret.first<<" "<<ret.second<<endl;
        }
    }

}