백준 13059번: Tourists (C++)

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

13059번: Tourists

---

Solved By: LCA, Number Theory

 

트리가 주어지면 각 노드의 배수 노드들 사이에 노드 개수를 세는 문제입니다.

트리이기에 LCA가 가능하고, Sparse Table을 사용했습니다. 그리고, 각 노드 사이의 거리(가중치)를 1이라 할당하고, 거리를 구하여 1을 더하면 노드의 개수이므로 이를 사용했습니다.

 

그리고, 각 노드의 배수들을 n 이하인 수들로 거리들을 구해야 합니다.

또한, n은 200,000 이하의 수라 노드의 수들을 다 더한 값이 int의 범위형을 넘을 수 있기 때문에 long long으로 거리 배열을 선언했습니다.

 

트리와 쿼리 2 (13511) 문제를 k번째 정점을 구하는 과정이 어려워서 이번 문제를 풀다가 힌트를 조금 얻어가는 거 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200001
#define LOG_MAX 19
#define pii pair<int, int>
#define ll long long
using namespace std;

vector<int> adj[MAX];
int level[MAX];
int parent[MAX][LOG_MAX];
ll dist[MAX][LOG_MAX];

int n;

void dfs(int now, int par){
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        if(next == par) continue;
        
        level[next] = level[now] + 1;
        parent[next][0] = now;
        dist[next][0] = 1;
        dfs(next, now);
    }
}

void parentSet(){
    for(int j = 1; j < LOG_MAX; j++){
        for(int i = 1; i <= n; i++){
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
            dist[i][j] = dist[parent[i][j - 1]][j - 1] + dist[i][j - 1];
        }
    }
}

void swap(int* a, int* b){
    int* temp = a;
    a = b;
    b = temp;
}

int lca(int a, int b){
    int ret = 0;
    if(level[a] < level[b]) swap(a, b);
    int diff = level[a] - level[b];
    
    for(int i = LOG_MAX - 1; i >= 0; i--){
        if(diff >= 1 << i){
            diff -= 1 << i;
            ret += dist[a][i];
            a = parent[a][i];
        }
    }
    
    if(a != b){
        for(int i = LOG_MAX - 1; i >= 0; i--){
            if(parent[a][i] != 0 && parent[a][i] != parent[b][i]){
                ret += (dist[a][i] + dist[b][i]);
                
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        ret += (dist[a][0] + dist[b][0]);
    }
    
    return ret;
}

int main(){
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    level[1] = 1;
    dfs(1, 0);
    parentSet();
    
    vector<pii> numMul;
    for(int i = 1; i <= n; i++){
        int j = i * 2;
        while(j <= n){
            numMul.push_back({i, j});
            j += i;
        }
    }
    
    ll result = 0;
    for(auto p : numMul){
        int lcaDist = lca(p.first, p.second);
        //cout << p.first << ' ' << p.second << '\n';
        //cout << lcaDist + 1 << '\n';
        result += (ll)(lcaDist + 1);
    }
    
    cout << result;
    return 0;
}