> 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_min,edge_len;
long long n, k, t,edge_total=0;
bool dfs_find(int idx,long long mid)
{
visit[idx] = true;
edge_len[idx] = 0;
vector<pair<long long, long long>> edges;
for (int i : edge[idx])
{
if (visit[i])continue;
if (dfs_find(i, mid)) return true;
if (mid <= edge_v[i])
{
edges.push_back({ edge_v[i], edge_len[i] });
}
if (edge_min[i] >= mid) {
edge_len[idx] = max(edge_len[i] + 1, edge_len[idx]);
}
if (edge_len[i] + 1 >= k && edge_total - edge_v[i] >= mid && edge_v[i] >= mid) {
//자를 수 있음.
return true;
}
}
sort(edges.begin(), edges.end());
int ii= -1;
int l =-1, r = -1;
for (int j = (int)edges.size() - 1; j >= 0; j--) {
while (ii + 1 < edges.size() && edge_total- edges[j].first - edges[ii + 1].first >= mid) {
ii++;
if (edges[ii].second > l) {//l값이 크고 r값이 작음
r =l;
l = edges[ii].second;
}
else if (edges[ii].second > r) {
r = edges[ii].second;
}
//이 과정이 잘 이해가 안갔는데 결국 k 값 이상되는 길이를 찾는 과정임.
}
if (ii == -1) {
continue;
}
if (edge_total - 2 * edges[j].first >= mid &&l== edges[j].second) {
//어 지금 제일 큰 길이와 동일하면 r을 써야함
if (r + edges[j].second + 2 >= k) {
return true;
}
}
else {
if (l + edges[j].second + 2 >= k) {
return true;
}
}
}
return false;
}
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_min[i] = min(edge_v[idx] - edge_v[i], edge_v[i]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int u,v;
cin >> t;
for (int a = 0; a < t; a++)
{
cin >> n >> k;
edge.assign(n, {});
edge_v.assign(n,0);
edge_min.assign(n, 0);
edge_len.assign(n, 0);
edge_total = 0;
visit.assign(n, false);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
edge_total += 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);
}
dfs(0);
long long l = 0, r = edge_total;
long long result = -1;
while(l<=r)
{
long long mid = (l + r) >> 1;
visit.assign(n, false);
if( dfs_find(0, mid))
{
l=mid+1;
result = mid;
}
else
{
r=mid-1;
}
}
cout << result << "\n";
}
return 0;
}
일단 어... 간선을 한 배열에
처음에 이렇게 생각했는데,
이게 아니고,
쭉 내려가서 올라오면서 누적하는 방식으로 모든 간선 가중치가 연결되어있어서 끊을 때 가중치 전체적인 값을 알 수 있게 되어있음.
일단은 dfs로 간선의 가중치 구성하는 구현방법과
이게 Bottom-up Subtree DP라는데 어쨌든, 여기까지 이해했고... 내일 또 진행 ㄱㄱ
일단 내 아이디어는 누적된 가중치로 제일 부모가 모든 가중치를 가지고 있잖아? 거기서 기준인 mid보다 그 노드의 실제 초기값이 크면 잘라도 되잖아? 자른후 b~뭐 리프 끝까지 합친 총 값은 그 다음 b에 있을 거 아냐? 그럼 a,b일단 통과 근데 k횟수니까 k가 2면 한번 더 잘라야겠지? 그럼 또 b도 그 mid범위 보다 큰지보고 크면 자르고 안되면 되는 자식으로 넘어가서 자르고값이 범위에 들어오는지 확인 그런다음에 이 경우가 여러가지 일거 아냐? 깊은 탐색으롲 ㅣㄴ행될 것이고? 잘랐을 때 mid범위에 들어온 조각들 이 존재하고, 그 조각들 중에서 가중치가 제일 큰 값만 따로 계산해서 벡터로 모은다음에 깊은탐색 끝나고 그 값 들중에 제일 큰값만 가져와서 정답을 갱신하면서 계속 mid줄이면서 파악하면 정답이 나오는것 맞나? <-오류 아이디어 ㅋㅋ;
select a simple path of exactly k edges and remove all edges on it.
음 문제를 잘못 이해한 듯.
연속된 k개의 간선을 잘라야하는 것;;
어 그러면 봐 a는 자식이 2개고 그 중에 1개에 자식이 4개임 그럼 경로가 하나는 k가 2이라 치면 a-자식-자식으로 존재하잖아? 이런 거 하나를 통째로 제거했을 때 남아있는 조각들이 k+1이 되고 거기서 계산해야한다는말 인것 같다?
상당한 난이도가 아닌가?;;
처음에 아무 간선이나 잘라도 되는 줄 알았다. 영어실력미스;;
뭔지 잘 몰랐는데 노드 개수가 아니라 그룹 형태의 조각 k+1개로 봐야함. 이렇게 보니 이해감.
아 일단 자식쪽에서 올라오면서 하는 바텀 업 형식으로 생각해야함. 나는 또 위에서 내려오는 식으로 생각;; 일단 내일도 조금씩 ㄱㄱ
코드를 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;
}
}
}
}아.. 일단
if (cst[j] >= mn) {
l[i] = max(l[j] + 1, l[i]);
}이 부분,
조건문은 부모제외 자식들을 모두 그룹으로 볼때 범위냐, 그니까 자를 수 있느냐? 라는 조건이고
그 다음에 현재 l배열은 그 노드에 딸린 간선의 수인데 매번 달라지는 이분탐색 조건값에 따라 사용될 변수로 r대신에 l을 사용한 것으로 보임.
그래서
if (cst[j] >= mn) {
l[i] = max(l[j] + 1, l[i]); 맨 하단 자식에서
}여기서 하단 자식에서 조건이 달성되면 간선이 있다라는 것을 0,+1 식으로 업데이트 해주고
일단 이분탐색쪽 바텀업 조건까지는 이해완료.
일단 이해한 내용을
정리를 해보자.
전체 범위로 이분탐색을 하는데 mid값을 기준으로
구간 설정된 그래프에서 그 mid값을 충족하는 k개의 edge len이 들어오는지 판단하고 들어온다면 그 기준으로 다시 이분탐색 mid값을 다시 범위를 줄여가면서
줄이는게 아니라,
정답이 작아진 조각의 크기가 제일 크게 해야되니까 l+1형식으로 해야할 듯,
while(true)
{
long long mid = (l + r) >> 1;
answer.assign(n, 0);
visit.assign(n, false);
if( dfs_find(0, mid))
{
l++;
}
else
{
r--;
}
}
}이렇게 l범위 늘려서 찾기.
계속 찾다가 마지막에 업데이트 된 값이 최적의 값이고 그 값을 정답으로 제출하면됨.
근데 dfs에서
구성을 edge_v는 그 노드에 붙은 모든 자식의 자식의 자식까지 포함한 가중치 값이고,
edge_min은 그 노드에서 간선이 잘려서 부모나 자식과 연결이 끊겼을 때의 최소값.
이렇게 dfs에서 구성을 해주고,
다시 이분탐색에서 dfs_find함수로 이분탐색 조건 탐색
똑같이 바텀업 형식으로 자식까지 쭉 내려간 뒤에 올라오면서 k횟수를 파악할 edge_len부분을 0+1형식으로 업데이트 해서 부모쪽에서 자식까지 몇개가 있는 지 파악하게 초기화
그 후 조건에 들어오면 true형식으로 리턴되면서 함수가 종료되게 하고
아니라면 자식들을 벡터에 담은 뒤 정렬하여서
최소~최대 범위 안에서 투포인터로
탐색하는데 아무래도 2개 이상일 때만 가능한 계산형태고
이 부분이 지금 헷갈림.
아 이게 그니까 만약에 k가 4인데 루트는 1개고 양쪽 트리 있고 그 양쪽 트리에 간선이 1개만 있으면 루트에서 아무리 자식 끝까지 내려가도 k는 4가 될 수 없지만
맨 마지막 왼쪽이나 오른쪽 자식부터 루트까지 올라온 뒤에 다시 반대쪽 리프노드까지 내려가면 4개의 간선형태 k를 만족함 이걸 구하는게 밑에 투포인터 부분인 것 같음.
일단 이게 투포인터 부분 뭔지는 알겠는데.. 막 머리로 다 어떻게 돌아가는지 판단이 잘안되고 있음. 그림으로 그려보는 게 좋을 것 같은데. 내일은 예제를 그림으로 그려보면서 정답이 나오는지 하나하나 판단해 보는 걸로...
다시다시
그림으로 예제 계산을 해보면서 코드진행도 따라가 보는 걸로...
일단 여기서 녹색부분으로 자르면 제일 최소값이 커지는 부위는 3~4 구간 간선을 잘라야
4쪽이 남아서 최소값 4가 되고 커진다. 서브트리는 6이고
결국 조각조각 내서 최소값을 모두 구해보면
1~2 자르면 1
2~3 자르면 3
3~$ 자르면 4
이 중에서 제일 큰게 4 니까 4가 정답이 된다.
물론 서브트리도 하나의 조각으로 보는 거고..
그러면 조각의 최소값이 커질려고 하면 가중치가 최대한 일정하게 자르는게 방향상 맞고.
코드도 그런식으로 이분탐색이 들어감. 그럼
저 정답을 구하려면 방식이 바텀 업이니까
1
4 1
1 2 3 4
1 2
2 3
3 4
이 예제로 나는 일단 2 가 나옴. 추적 디버깅 ㄱㄱ
아 내가 dfs함수로 edge_v값을 만들어 두지 않음.
일단 4가 나오는 것은 확인
/*sort(edges.begin(), edges.end());
int ii= -1;
int l = -1e5, r = -1e5;
for (int j = (int)edges.size() - 1; j >= 0; j--) {
while (ii + 1 < edges.size() && edge_total- edges[j].first - edges[ii + 1].first >= mid) {
ii++;
if (edges[ii].second > l) {
r =l;
l = edges[ii].second;
}
else if (edges[ii].second > r) {
r = edges[ii].second;
}
}
if (ii == -1) {
continue;
}
if (edge_total - 2 * edges[j].first >= mid &&l== edges[j].second) {
if (r + edges[j].second + 2 >= k) {
return true;
}
}
else {
if (l + edges[j].second + 2 >= k) {
return true;
}
}
}*/이 주석친 코드는 예제 1번에 필요없는 단일 방향이고 k횟수도 1번이라 쓰일 일도 없을 듯? 정답 4나옴.
어 일단 보면 예제가
1
7 2
7 1 3 2 2 4 3
1 2
2 3
2 4
2 5
5 6
5 7
이 부분에서는 2번 노드가 자식이 3,4,5로 방향이 여러개로 갈린다.
이걸 직접 그림으로 보면
대충 작은 값 생각해서 잘라봤는데 이게 정답 같은?;;
그럼 이걸 맨 마지막 리프노드에서 부터 거슬러 올라면서 정답을 추적하려고 해봐야하는데...아 이거는 공책에 좀 계산을 해봐야겠다. 일단 여기까지...
어 일단 어느 정도 조건 분기를 이해가 되어갔는데..
아직도 리프노드 한쪽과 현재 부모노드가 중간에 연결된 노드 역할 하는 식으로 쓰이고 다른 자식이 또 마지막 노드형식으로 되는 길을 찾는 로직이 이해가 잘 안감..
아 일단 정답이 안나온게 범위랑 ios_base::sync_with_stdio(false); 요곳도 NULL이 문제가 있을 수 있는 것 같아서 false로 바꿈. 통과는 됐지만 솔직히 막 엄청 머리로 계산 시뮬레이션 돌릴 정도로 이해하진 못함. ㅠㅠ
