1289 트리의 가중치, 14432 우물

1289 트리의 가중치 https://www.acmicpc.net/problem/1289
14432 우물 https://www.acmicpc.net/problem/14432

1. 트리의 가중치
트리의 모든 에지에 음이 아닌 정수인 가중치가 배정되었다. 
‘경로의 가중치’란 경로에 해당하는 에지들의 곱으로 정의된다. 
또한 ‘트리의 가중치’는 트리 상에 가능한 모든 경로에 대해 ‘경로의 가중치’의 합을 의미한다. 
문제는 트리가 주어졌을 때 ‘트리의 가중치’를 구하는 것이다.

딱봐도 subtree에 처리를 해서 해결하는 방식으로 풀어야만 할것같이 보인다.

밑의 tree에서 1에서 dfs를 돌리고 현재 2→4로 가는 간선에 있다고 가정한다.

트리의 가중치를 구하는 방법은 내 기준으로 4가지로 나누어 구했다.
먼저 위의 한가지 빨간경로와 다음의 3가지 경로이다.

초록색 경로가 해당 경로다.

코드에서 subtree배열에는 맨 위의 그림경로와 위의 첫번째 그림의 경로를 누적해 저장해준다.

#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ll; int N; const ll mod = (ll)(1e9 + 7); ll subtree[100001]; vector<pair<int, int>> adj[100001]; bool v[100001]; ll ans = 0; void dfs(int here) {     v[here] = true;     for (auto &n : adj[here]) {         int next = n.second;         int cost = n.first;         ll plus = 0;         if (v[next]) continue;         dfs(next);         plus += (ll)cost;         plus %= mod;         plus += ((ll)cost)*(subtree[next]) % mod;         plus %= mod;           ans += ((ll)cost)*(subtree[here]) % mod;         ans %= mod;         ans += plus;         ans %= mod;         ans += ((((ll)cost*(subtree[here])) % mod)*subtree[next]) % mod;         ans %= mod;         subtree[here] += plus;         subtree[here] %= mod;     } } int main() {     scanf("%d", &N);     for (int n = 0;n < N - 1;n++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d,v });         adj[v].push_back({ d,u });     }     dfs(1);     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

2. 우물

마을에 우물을 설치하면 인접한 마을 우물과 현재 우물에도 그 수만큼 설치가된다.

각 마을에 필요한 우물수가 주어질 때 최소 우물 개수를 구하는 문제다.(tree에서)

설명은 이것으로 대체한다.

http://wookje.dance/2017/02/12/mugcup-solution/

#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ll; int N, M; int cost[100001]; vector<int> adj[100001]; ll ans = 0; void dfs(int here, int prev) {     int get = 0;     for (int next : adj[here]) {         if (next == prev) continue;         dfs(next, here);         get = max(get, cost[next]);     }     ans += (ll)get;     cost[here] -= get;     for (int next : adj[here]) {         cost[next] -= get;     } } int main() {     scanf("%d%d", &N, &M);     for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);     for (int m = 0;m < M;m++) {         int u, v;         scanf("%d%d", &u, &v);         adj[u].push_back(v);         adj[v].push_back(u);     }     dfs(1, -1);     if (cost[1] > 0) ans += cost[1];     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

2515 전시장

백준 2515 전시장 https://www.acmicpc.net/problem/2515

문제가 좀 까다로워 보인다. 그림을 배치하는데 세로 기준으로 보이는 부분이 S이상인 것에 대해서만 구입을 해서 최대화 시켜야한다. N의 범위또한 상당히 크다.

하지만 문제를 단순화 시키면 풀만한 문제이다.
사실상 그림이 가려진다는것은 그 그림을 배치하지 않는다는것과 동치이다.

따라서 그림을 높이순으로 오름차순, 가격을 내림차순으로 정렬한 후 [1, N] 구간의 그림을 선택하는 문제로 바뀐다.

DP를 적용시키고 높이 차이가 S이상인 지점을 찾는것은 이분탐색으로 찾으면 된다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Paint{     int v, h; }; bool cmp(const Paint &a, const Paint &b){     if (a.h == b.h)         return a.v > b.v;     return a.h < b.h; } Paint paint[300001]; int N, S; int dp[300001][2];     int diff[300001]; int binary_search(int n){     int l = 0, r = n - 1;          while (l <= r){         int mid = (l + r) / 2;         if (paint[n].h - paint[mid].h >= S) l = mid + 1;         else r = mid - 1;     }     return r; } int main(){     scanf("%d%d", &N, &S);     for (int n = 1; n <= N; n++)         scanf("%d%d", &paint[n].h, &paint[n].v);       sort(paint + 1, paint + N + 1, cmp);     paint[0].h = paint[0].v;       for (int n = 1; n <= N; n++){                 if (paint[n].h - dp[n - 1][1] >= S){            //차이가 S이상일때는 바로 더함             dp[n][0] = dp[n - 1][0] + paint[n].v;             dp[n][1] = paint[n].h;         }         else{             int prev;        // n과의 높이 차이가 S이상인 지점             prev = binary_search(n);             if (dp[n - 1][0] > dp[prev][0] + paint[n].v){ //현재 그림과 더했지만 유지되는 가치가 더 클 때                 dp[n][0] = dp[n - 1][0];                 dp[n][1] = dp[n - 1][1];             }             else{                                         //현재 그림과 높이차이가 가장 작게나는 가치가 더 클 때                 dp[n][0] = dp[prev][0] + paint[n].v;                 dp[n][1] = paint[n].h;             }         }     }     printf("%d\n", dp[N][0]);     return 0; } Colored by Color Scripter

cs

(LCA - Lowest Common Ancestor) 1761 정점들의 거리

백준 1761 정점들의 거리 https://www.acmicpc.net/problem/1761
3176 도로 네트워크 https://www.acmicpc.net/problem/3176
Codeforces #425 (Div. 2) D - Misha, Grisha and Underground  
http://codeforces.com/contest/832/problem/D

LCA (최소 공통 조상) 
어떤 두 정점의 가장 가까운 공통 루트가 누구인지 알아내는 문제이다.
종만북에는 세그먼트 트리로 LCA를 구하지만 넘 복잡하고 보통 DP를 이용해서 구한다.

DFS로 노드들의 depth를 구한 후 $2^K$위의 루트 노드가 무엇인지 DP를 이용하여 전처리한다.
여기서 정점사이의 거리나 최소거리 등의 정보도 함께 넣을 수 있다.

1. 정점들의 거리
트리에서 두 정점 사이의 거리를 구하는 문제이다. 
전처리 할 때 현재 노드에서 $2^K$위의 루트 노드 까지 거리도 전처리 해준다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define INF 987654321 int N, M; vector<pair<int, int>> adj[40001]; bool visit[40001]; int depth[40001], par[40001][17], dist[40001][17]; void dfs(int here, int d){     visit[here] = true;     depth[here] = d;     for (auto n : adj[here]){         int next = n.second;         int cost = n.first;         if (!visit[next]){             par[next][0] = here;             dist[next][0] = cost;             dfs(next, d + 1);         }     } } void dp(){     for (int m = 1; m < 17; m++){         for (int n = 1; n <= N; n++){             par[n][m] = par[par[n][m - 1]][m - 1];             dist[n][m] = dist[n][m - 1] + dist[par[n][m - 1]][m - 1];         }     } } int lca(int u, int v){     int ret = 0;     if (depth[u] < depth[v]) swap(u, v);     for (int i = 16; i >= 0; i--){         if (depth[u] - depth[v] >= (1 << i)){             ret += dist[u][i];             u = par[u][i];         }     }     //depth같아짐     if (u == v) return ret;     for (int i = 16; i >= 0; i--){         if (par[u][i] != par[v][i]){             ret += (dist[u][i] + dist[v][i]);             u = par[u][i], v = par[v][i];         }     }     ret += (dist[u][0] + dist[v][0]);     return ret; } int main(){     scanf("%d", &N);     for (int n = 0; n < N - 1; n++){         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d, v });         adj[v].push_back({ d, u });     }     //전처리     dfs(1, 0);     dp();     scanf("%d", &M);     while (M--){         int a, b;         scanf("%d%d", &a, &b);         printf("%d\n", lca(a, b));     }     return 0; } Colored by Color Scripter

cs

2. 도로 네트워크
문제를 잘 읽어보면 네트워크는 트리형태이다.
이 문제에서는 최소 간선, 최대 간선에 대해 전처리 해주면 된다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define INF 987654321 int N, K; vector<pair<int, int>> adj[100001]; bool visit[100001]; int depth[100001]; int par[100001][21]; int edge_min[100001][21], edge_max[100001][21]; void dfs(int here, int d){     visit[here] = true;     depth[here] = d;     for (auto n : adj[here]){         int next = n.second;         int cost = n.first;         if (!visit[next]){             par[next][0] = here;             edge_min[next][0] = cost;             edge_max[next][0] = cost;             dfs(next, d + 1);         }     } } void dp(){     for (int n = 1; n < 21; n++){         for (int m = 1; m <= N; m++){             par[m][n] = par[par[m][n - 1]][n - 1];             edge_min[m][n] = min(edge_min[m][n - 1], edge_min[par[m][n - 1]][n - 1]);             edge_max[m][n] = max(edge_max[m][n - 1], edge_max[par[m][n - 1]][n - 1]);         }     } } pair<int,int> lca(int a, int b){     int rmin = INF, rmax = -INF;     if (depth[a] < depth[b]) swap(a, b);     for (int i = 20; i >= 0; i--){         if (depth[a] - depth[b] >= (1 << i)){             rmin = min(rmin, edge_min[a][i]);             rmax = max(rmax, edge_max[a][i]);             a = par[a][i];         }     }     if (a == b) return { rmin, rmax };     for (int i = 20; i >= 0; i--){         if (par[a][i] != par[b][i]){             rmin = min(rmin, min(edge_min[a][i], edge_min[b][i]));             rmax = max(rmax, max(edge_max[a][i], edge_max[b][i]));             a = par[a][i];             b = par[b][i];         }     }     rmin = min(rmin, min(edge_min[a][0], edge_min[b][0]));     rmax = max(rmax, max(edge_max[a][0], edge_max[b][0]));     return { rmin, rmax }; } int main(){     scanf("%d", &N);     for (int n = 0; n < N - 1; n++){         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d, v });         adj[v].push_back({ d, u });     }     //전처리     dfs(1, 0);     dp();     scanf("%d", &K);     for (int k = 0; k < K; k++){         int D, E;         scanf("%d%d", &D, &E);         pair<int,int> ans = lca(D, E);         printf("%d %d\n", ans.first, ans.second);     }     return 0; } Colored by Color Scripter

cs

3. Codeforces #425 (Div. 2) - D

나의 첫 codeforces 대회였다. 

2시간이라는 촉박한 시간과 영어여서 문제이해하는데도 한참 걸렸다.

(그리고 Div. 2 치고 어렵게 나온거같다;; 1문제 품)

B는 문자열, C는 수식과 실수가 나와서 바로넘어갔었다.

D를 실제로 C보다 더 많이 풀었는데 대회때는 못풀었지만 그나마 풀만했던거같다.

트리가 존재한다. Misha는 $s$->$f$를 가며 정점에 낙서를 하고 Grisha는 $f$->$t$를 이동하며 

낙서된 정점의 수를 세는데 Grisha가 세는 정점의 수의 최댓값을 구하는 문제이다.

각 쿼리에는 $s$, $f$, $t$의 후보 $a$, $b$, $c$가 주어진다.

대회때는 2820 자동차 공장풀듯이 세그먼트트리와 lazy propogation 그리고 LCA를 이용해서 풀려고 했지만 끝나고서야 오류를 알았다.

사실은 LCA만으로 풀리는 문제이다.

1. LCA($s$, $f$) == LCA($f$, $t$) == $f$인 경우

2. LCA($s$, $f$) == LCA($f$, $t$) != $f$인 경우

3. LCA($s$, $f$) != LCA($f$, $t$)인 경우에 대해 따져주면 된다.

쿼리에서 입력으로 들어오는 후보가 3개밖에없으니 $3!$으로 모든 경우에 대해 돌려주어 최댓값을 구하면 된다.

int solve(int s, int f, int t) {     int ret = 0;     int sf_lca = getLCA(s, f), ft_lca = getLCA(f, t);     if (sf_lca == ft_lca && sf_lca == f) ret = depth[getLCA(s, t)] - depth[f];     else if (sf_lca == ft_lca) {         int common_lca = sf_lca;         ret = depth[getLCA(s, t)] - depth[common_lca] + depth[f] - depth[common_lca];     }     else{         if (depth[sf_lca] > depth[ft_lca]) ret = depth[f] - depth[sf_lca];         else ret = 0;     }     return ret + 1; } Colored by Color Scripter

cs