오늘부터는 네이버 블로그 말고 벨로그를 활용하여 공부한 내용을 기록하고,
블로그에는 좀 정리해서 한 글로 만드는 걸로...
> F. Momoyo and the Network
time limit per test3 seconds
memory limit per test256 megabytes
Where Is That Bustling Marketplace Now— Unconnected Marketeers
The Underground Great Line Network is a grand transit system connecting all corners of Gensokyo. Momoyo noticed that the network's layout resembled a tree∗ structure. She couldn't help but imagine the most effective way to dismantle that tree.
Given a tree with n nodes where node i has weight ai, select a simple path of exactly k edges and remove all edges on it. This splits the tree into k+1 connected components, each with weight equal to the sum of its nodes' weights. You need to maximize the minimum component weight, or output −1 if no simple path of exactly k edges exists.
∗A tree is a connected graph without cycles.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and k (1≤k≤n−1, 2≤n≤2⋅105).
The second line contains n integers, where the i-th integer represents ai (1≤ai≤109).
The next n−1 lines each contain two integers u and v, representing an edge of the tree.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
Output
> For each test case, output the maximum possible minimum component weight, or −1 if no such path exists.cpp
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <list>
#include <random>
#include <numeric>
#include <string>
#include <algorithm>
#include <cmath>
#include<chrono>
#include<iomanip>
using namespace std;
vector<long long>sm;
vector<long long>a;
long long tot = 0;
vector<bool>used;
vector<vector<int>>r;
vector<long long>cst;
void dfs(int i) {
used[i] = true;
sm[i] = a[i];
vector<int>h;
for (auto j : r[i]) {
if (!used[j]) {
dfs(j);
h.push_back(j);
sm[i] += sm[j];
}
}
for (auto j : h) {
cst[j] = min(sm[j], sm[i] - sm[j]);
}
//방문한 놈은 다시 방문안하고 쭉 진행하면서 모든 간선을 이동하고 이동한 놈의 가중치에 간선
//연결된 놈중에 방문했던 놈들은 누적해주는 식으로 sm값이 초기화되는 것 같음. 그렇게 하고
//방문된 간선들을 모아서 다시 그 간선들이 방문해서 초기 가중치 값을 부여받았다면
//끊어졌을때 값이랑 그니까 왼쪽 오른쪽 끊어졌을 때 값중 작은값을 cst에 초기화하는 것 같음?
}
vector<int>l;
bool ans = false;
long long k;
void dfs2(int i, long long mn) {
used[i] = true;
l[i] = 0;
vector<pair<long long, int>>t;
for (auto j : r[i]) {
if (!used[j]) {
dfs2(j, mn);
if (sm[j] >= mn) {
t.push_back({ sm[j],l[j] });
}
if (cst[j] >= mn) {
l[i] = max(l[j] + 1, l[i]);
}
if (l[j] + 1 >= k and tot - sm[j] >= mn and sm[j] >= mn) {
ans = true;
}
}
}
sort(t.begin(), t.end());
int i1 = -1;
int mx1 = -1e5, mx2 = -1e5;
for (int j = (int)t.size() - 1; j >= 0; j--) {
while (i1 + 1 < t.size() and tot - t[j].first - t[i1 + 1].first >= mn) {
i1++;
if (t[i1].second > mx1) {
mx2 = mx1;
mx1 = t[i1].second;
}
else if (t[i1].second > mx2) {
mx2 = t[i1].second;
}
}
if (i1 == -1) {
continue;
}
if (tot - 2 * t[j].first >= mn and mx1 == t[j].second) {
if (mx2 + t[j].second + 2 >= k) {
ans = true;
}
}
else {
if (mx1 + t[j].second + 2 >= k) {
ans = true;
}
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vector<long long>st(20, 1);
for (int i = 1; i <= 18; i++) {
st[i] = st[i - 1] * 10;
}
//이거는 1,10,100 이렇게 증가해서 18이니까 0이 18개까지 붙는 값으로 증가하는 배열 st같음
int t = 1;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> k;
a.assign(n, 0);//벡터를 n개 0으로초기화
tot = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
tot += a[i];//토탈 가중치 구함
}
r.assign(n, {});//벡터안에 벡터 식으로 구현 n개 2차 벡터
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;//0으로 인덱스 줄여서 단일 방향이지만 양쪽 간선 구현
r[u].push_back(v);
r[v].push_back(u);
}
used.assign(n, 0);
sm.assign(n, 0);
cst.assign(n, 0);//전부 n크기의 벡터
dfs(0);//여기서 일단 일차적으로 각 간선을 끊었을 때 최소한의 가중치를 ctj를 구하는 것 같고
long long l1 = -1, r1 = 1e14;//전체 범위로 이분탐색하면서
while (l1 + 1 != r1) {
long long m = (l1 + r1) / 2;
l.assign(n, 0);
used.assign(n, 0);//다시 재사용
ans = false;
dfs2(0, m);
if (ans) {
l1 = m;
}
else {
r1 = m;
}
}
cout << l1 << '\n';
}
}정답코드 분석 중..
내 코드
cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long arr[200001];
vector<vector<int>> edge;
vector<bool> visit;
vector<long long> edge_v,edge_cal;
void dfs(int idx)
{
visit[idx] = true;
edge_v[idx] = arr[idx];
vector<int> e;
for (int i : edge[idx])
{
if (visit[i])continue;
dfs(i);
edge_v[idx] += edge_v[i];
e.push_back(i);
}
for (int i:e)
{
edge_cal[i] = min(edge_v[idx] - edge_v[i], edge_v[i]);
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int t, n, k,u,v;
cin >> t;
for (int a = 0; a < t; a++)
{
cin >> n >> k;
edge.assign(n, {});
edge_v.assign(n,0);
edge_cal.assign(n, 0);
visit.assign(n, false);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n-1; i++)
{
cin >> u >> v;
u--;
v--;
edge[u].push_back(v);
edge[v].push_back(u);
}
}
return 0;
}일단 어... 간선을 한 배열에
처음에 이렇게 생각했는데,
이게 아니고,
쭉 내려가서 올라오면서 누적하는 방식으로 모든 간선 가중치가 연결되어있어서 끊을 때 가중치 전체적인 값을 알 수 있게 되어있음.
일단은 dfs로 간선의 가중치 구성하는 구현방법과
이게 Bottom-up Subtree DP라는데 어쨌든, 여기까지 이해했고... 내일 또 진행 ㄱㄱ
