3176 도로 네트워크

https://www.acmicpc.net/problem/3176

parent[i][j] = 노드 i의 2^j번째 조상

maxd[i][j] = 노드 i부터 2^j번째 조상까지의 간선 중 최대값

mind[i][j] = 노드 i부터 2^j번째 조상까지의 간선 중 최소값

#include <cstdio>
#include <vector>
#include <algorithm>
#define N 100005
#define INF 987654321
using namespace std;
 
int n,m,u,v,w,maxv,minv;
int parent[N][21],check[N],depth[N],maxd[N][21],mind[N][21];
vector<pair<int,int>> a[N];
 
void dfs(int now,int d)
{
    check[now]=true;
    depth[now]=d;
    for(auto i : a[now])
    {
        int next=i.first,cost=i.second;
        if(check[next]) continue;
        parent[next][0]=now;
        maxd[next][0]=cost;
        mind[next][0]=cost;
        dfs(next,d+1);
    }
}
 
void lca(int x,int y) {
    if(depth[x]>depth[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(depth[y]-depth[x]>=(1<<i))
        {
            maxv=max(maxv,maxd[y][i]);
            minv=min(minv,mind[y][i]);
            y=parent[y][i];
        }
    }
    if(x==y) return;
    for(int i=20;i>=0;i--)
    {
        if(parent[x][i]!=parent[y][i])
        {
            maxv=max(maxv,max(maxd[x][i],maxd[y][i]));
            minv=min(minv,min(mind[x][i],mind[y][i]));
            x=parent[x][i],y=parent[y][i];
        }
    }
    maxv=max(maxv,max(maxd[x][0],maxd[y][0]));
    minv=min(minv,min(mind[x][0],mind[y][0]));
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    dfs(1,1);
    for(int j=1;j<21;j++)
    {
        for(int i=1;i<=n;i++)
        {
            parent[i][j]=parent[parent[i][j-1]][j-1];
            maxd[i][j]=max(maxd[i][j-1],maxd[parent[i][j-1]][j-1]);
            mind[i][j]=min(mind[i][j-1],mind[parent[i][j-1]][j-1]);
        }
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %d",&u,&v);
        maxv=-INF,minv=INF;
        lca(u,v);
        printf("%d %d\n",minv,maxv);
    }
    return 0;
}