[BOJ 10403] Intrepid climber

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

10403번: Intrepid climber

Tag : Greedy, Tree dp

 

문제요약

트리 위에 F개의 랜드마크가 존재하는데, 1번노드에서 출발해 모든 랜드마크를 지나는 가장 짧은 자취의 길이를 구하라.

(내려가는 간선만 포함)

 

풀이

최적의 자취는 1번에서 출발해 모든 랜드마크를 지난 뒤 어떠한 랜드마크에서 탐색을 종료하는 것이다.

1번에서 출발해 1번으로 돌아오는 최적의 자취를 생각해보면 모든 랜드마크를 지나기위한 간선들이 한번씩 포함된 자취이다.

여기서 가장 거리가 먼 랜드마크의 거리를 하나 빼주면 답이된다.

 

코드에서의 \(sz_i\)는 i의 서버트리에 존재하는 랜드마크의 개수이다. \(sz_i\)가 양수라면 해당 간선은 항상 자취에 포함된다.

 

 

시간복잡도 : \(O(N+M)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,M;
int chk[101010];
int sz[101010];
ll dep[101010],mx=0,sum=0;
vector<pi>v[101010];

void dfs(int x,int pre){
    if(chk[x])rmax(mx,dep[x]);
    sz[x]=chk[x];
    for(auto&[i,j]:v[x]){
        dep[i]=dep[x]+j;
        dfs(i,x);
        if(sz[i])sum+=j;
        sz[x]+=sz[i];
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>M;
    for(int i=1;i<=N-1;i++){
        int p,q,r;cin>>p>>q>>r;
        v[p].pb({q,r});
    }
    for(int i=1;i<=M;i++){
        int x;cin>>x;
        chk[x]=1;
    }
    dfs(1,0);
    ll ans=sum-mx;
    cout<<ans<<endl;
}