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;
}
| cs |
2. 우물
마을에 우물을 설치하면 인접한 마을 우물과 현재 우물에도 그 수만큼 설치가된다.
각 마을에 필요한 우물수가 주어질 때 최소 우물 개수를 구하는 문제다.(tree에서)
설명은 이것으로 대체한다.
#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;
}
| cs |
