백준 13510 (C++) 트리와 쿼리 1

최초 업로드: 2025-04-21 20:33:49

최근 수정 시간: 2025-07-25 09:25:40

게시자: rlatjwls3333

카테고리: 백준

# [Platinum I] 트리와 쿼리 1

#### [문제 링크](https://www.acmicpc.net/problem/13510)

## 문제 설명

N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.

아래의 두 쿼리를 수행하는 프로그램을 작성하시오.

## 입력

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 비용 w가 주어진다.

다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

간선의 비용은 항상 1,000,000보다 작거나 같은 자연수이다.

## 출력

각각의 2번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

## 풀이
#### 간선 i에서의 cost를 더 깊은 노드에서 올라올 때 드는 비용으로 두고 heavy-light-decomposition 알고리즘을 써서 풀면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 100000;

struct edge {
    int u, v, c;
};

int subTreeCnt[MAX];
int _size, arr[MAX*3];
vector<edge> edges(MAX);
int edgeNum[MAX];
vector<vector<int>> conn(MAX), child(MAX);
int nodeCnt, nodeNum[MAX], groupCnt, groupNum[MAX], head[MAX], parent[MAX], depth[MAX];

void dfs1(int cur) {
    subTreeCnt[cur]=1;
    for(int next:conn[cur]) {
        if(!subTreeCnt[next]) {
            dfs1(next);
            subTreeCnt[cur] += subTreeCnt[next];
            child[cur].push_back(next);
            if(subTreeCnt[child[cur].front()] > subTreeCnt[child[cur].back()]) swap(child[cur].front(), child[cur].back());
        }
    }
}

void dfs2(int cur, int curDepth) {
    int u = nodeNum[cur] = nodeCnt++;
    depth[u] = curDepth;

groupNum[u] = groupCnt;
    if(head[groupCnt]==-1) head[groupCnt]=u;

if(child[cur].empty()) {
        groupCnt++;
        return;
    }
    for(int next:child[cur]) {
        dfs2(next, curDepth+1);
        parent[nodeNum[next]] = u;
    }
}

void construct(int n) {
 _size=1;
 while(_size<n) _size<<=1;
 _size<<=1;

for(int i=0;i<n-1;i++) {
 int u = nodeNum[edges[i].u];
 int v = nodeNum[edges[i].v];
 if(depth[u]>depth[v]) edgeNum[i] = u;
 else edgeNum[i] = v;
 arr[edgeNum[i]+_size/2] = edges[i].c;
 }
 for(int i=_size/2-1;i>0;i--) arr[i] = max(arr[i*2], arr[i*2+1]);
}

void update(int i, int c) {
    i = edgeNum[i]+_size/2;
    arr[i] = c;
    while(i>1) {
        i>>=1;
        arr[i] = max(arr[i*2], arr[i*2+1]);
    }
}

int search(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum];
 int mid = (nodeL+nodeR)/2;
 return max(search(L, R, nodeNum*2, nodeL, mid), search(L, R, nodeNum*2+1, mid+1, nodeR));
}

int query(int u, int v) {
    int res=0;
    u = nodeNum[u];
    v = nodeNum[v];
    while(groupNum[u]!=groupNum[v]) {
        int uHead = head[groupNum[u]], vHead = head[groupNum[v]];
        if(depth[uHead]>depth[vHead]) {
            res = max(res, search(uHead, u));
            u = parent[uHead];
        } else {
            res = max(res, search(vHead, v));
            v = parent[vHead];
        }
    }
    return max(res, search(min(u, v)+1, max(u, v)));
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n-1;i++) {
 cin >> edges[i].u >> edges[i].v >> edges[i].c;
 edges[i].u--;
 edges[i].v--;
 conn[edges[i].u].push_back(edges[i].v);
 conn[edges[i].v].push_back(edges[i].u);
 }

dfs1(0);
    memset(head, -1, sizeof head);
    dfs2(0, 0);

construct(n);

int m; cin >> m;
 while(m--) {
 int a, b, c; cin >> a >> b >> c;
 if(a==1) {
 update(b-1, c);
 } else {
 cout << query(b-1, c-1) << '\n';
 }
 }
}
```