[Codeforces 1084D] The Fair Nut and the Best Path

[Codeforces 1084D] The Fair Nut and the Best Path

문제 설명 : 

n개의 노드가 있는 트리가 있다. 각 노드에는 양의 가중치가 있으며, 노드 간의 간선에도 가중치가 있다. 노드를 지날 때는 그 노드에 배정된 가중치 만큼 값을 더할 수 있으며, 간선을 지날 때에는 그 간선에 배정된 가중치 만큼 가중치가 차감된다. 이때 얻을 수 있는 최대의 가중치의 합을 구하는 문제이다. 각 노드는 단 한번만 방문이 가능하며, 시작 지점은 어디든 상관없다.

풀이 : 

이 문제에서의 가장 중요한 이슈는 트리를 순회하면서 앞으로 갈 노드(next)를 방문하는 것이 이득일지 아닐지에 대한 문제이다. 이를 구하는 함수가 dfs(next)인데, 이 dfs(next)의 반환값이 양수라면 방문하는 것이 이득이고, 음수라면 방문하지 않는 것이 이득이다. 

그리고 모든 노드는 단 한 번만 방문이 가능하기 때문에 다시 되돌아 갈 수 없다. 따라서 여러 갈래 길이 나왔을 때 가장 가중치가 큰 길을 선택해야 한다.  내가 이 문제를 풀면서 가장 애를 먹었던 문제는 dfs로 노드를 순회하다가 2개 이상의 갈림길이 나왔을 때이다. 즉 현재 지나온 경로(=prev)가 아닌 다른 두개 이상의 경로가 있을 때는 다음과 같은 두 가지 케이스중에서 더 큰 가중치를 선택해야 한다.

1. 현재 지나온 경로의 가중치 + 다른 경로들 중에서 가장 큰 가중치

2. (현재 경로를 포기하고) 다른 경로 중에서 1번째와 2번째로 큰 가중치

1번을 구하는 식이 max1+w[node](63줄)이고 이 값은 현재 node를 호출한 함수( dfs(prev) )로 반환될 것이므로 그 함수에서 현재 값을 전달받아 계산할 것이다.

2번을 구하는 식은 max1+max2+w[node](62줄)이다.

둘 중 큰 값이 정답이 된다.

주의할 점 : 

-

배운 점 : 

54~61줄에 가장 큰 값과 두 번째로 큰 값을 찾는 조건문이 구현되어 있다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
/****************************Contest Template******************************/
const int SIZE= 300009;
const ll N_INF=-(1LL<<62);
 
int w[SIZE];
vector<pii> graph[SIZE];
ll ans=0;
 
ll dfs(int prev,int node){
    ll cur_max=0;
    ll max1=0,max2=0;
    for(auto nx:graph[node]){
        int next=nx.first,next_cost=nx.second;
        if(next==prev) continue;
 
        cur_max=dfs(node,next)-next_cost;
        if(max1<cur_max){
            max2=max1;
            max1=cur_max;
        }
        else if(max2<cur_max){
            max2=cur_max;
        }
    }
    ans=max(ans,max1+max2+w[node]);
    return max1+w[node];
}
 
int main(){
    int n;    scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&w[i]);
    }
 
    for(int i=1 ; i<=n-1 ; i++){
        int u,v,c;    scanf("%d %d %d",&u,&v,&c);
        graph[u].push_back({v,c});
        graph[v].push_back({u,c});    
    }
 
    dfs(0,1);
 
    printf("%lld\n",ans);
 
    return 0;
}