COFO::1337C Linova and Kingdom

• Link : COFO::1337C

Problem

• level : 1600
• tag : dfs and similar, dp, greedy, sortings, trees
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit and solve with edit: 40
  • Tried to solve the problem before read edit :

Point

• There are n cities
• Choose k industry cities and get the maximum happiness of them

Design

• This is the crucial fact,
  • When we choose node v as industry, then all of hildren of v should be industry
  • If not, it’s not the way to make happiness maximum
• During solving the problem, I could come up with idea that I need to get depth and size of children of every node
• But, the reason I couldn’t solve it was I couldn’t figure out how to use it even though I felt these factors are going to be used somehow
• Because,
  • As I said earlier, if v is industry, subtree of v should be industry
  • It means, I can choose industry from leaf nodes, but couldn’t handle them all correctly
• But here’s the edit’s way that makes the solution way easier
• Let’s say all cities are tourism, then think about it would be changed to industry
  • Then how happniess changed?
  • size[i] : size of subtree of node i
  • depth[i] : nodes count on the path(1, i)
• Then we can get dms[i] : -(depth[i] - 1) + (size[i] - 1), if we change node i from industry to tourism
  • -(depth[i] + 1) : since i is no longer the industry, depth from the node to the root(which is happiness) should be deduct from the sum
  • (size[i] - 1) : Since node i is tourism city, the children of the node would get +1 happiness for all of them
• Now we sort dms and choose largest n - k cities and add up the happiness
• But, how can this sort and stuff works? I wondered..
• Because, with this way, how can we sure that the fact (if node v is industry, the children of v should be industry) ?
  • What if the b is tourism and a and c are industry ? (when a - b - c are contected, and a is the parent of b )
• Now I understood, why above circumstance can not happen from the first place
• Because,
  • dms[a] > dms[b] > dms[c] stands if a is parent of b and b is parent of c
  • As I said, dms[i] = size[i] - depth[i]
  • We know that size[b] is smaller than size[a] and depth[b] is greater than depth[a]
  • dms[a] = size[a] - depth[a] > dms[b] = size[b] - depth[b]

Thought process

. root 는 무조건 tourism 으로 하는게 이득
  . 모든 경로에 포함되므로
. 나머지 k - 1 개의 industry 의 위치를 정해야한다.
. 무조건, root 에서 거리가 먼 순으로 정하면 되는게 아님
  . 그럼 경로가 겹쳐서 합이 줄어들 수 있음 -> TC3

. 일단, leaf 노드에서부터 정하는 건 맞음
. 그러다가, leaf 의 갯수가 줄어들 수도있음
  . 분기점에서 만나면 (TC3 의 7 처럼)


. 각 지점에서 root 까지의 거리를 알고 있어야함.
. 그리고, 새로운 industry 가 정해질때마다,
  . 해당 industy 를 부모로하는 애들의 갯수 + 1(자기자신) * 남은 거리로 대체되어야함


int lenToRoot[n]; // i 번째 시티에서 root 까지의 거리
bool isIndusty[n]; // i 번째 시티가 industry 인지 구분


int childCnt[i]; // i 번째 시티의 자식 갯수
int industryHere[i]; // i 번째 시티의 leaf 에서 i번째 city 까지 industry 인 경우 더해지는 행복지수
	: 총 childCnt[i] + 1 개가 사용될 거고,
: 행복은 += (childCnt[i] + 1) * lenToRoot[i]

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
const int MAXN = 2 * 1e5 + 9;

int n, k;
vector<int> grp[MAXN];
int depth[MAXN];
int _size[MAXN];
int dms[MAXN]; // dms[i] : i 번째 도시가 industry 에서 tourist 가 되면, 얻게되는 행복의 합.
int dfs(int cur, int pcur) {
    depth[cur] = depth[pcur] + 1;
    
    int sz = 1;
    for(auto v : grp[cur]) {
        if (depth[v] == 0)
            sz += dfs(v, cur);
    }
    _size[cur] = sz;
    dms[cur] = -(depth[cur] - 1) + (_size[cur] - 1);
    return sz;
}
void solve() {
    cin >> n >> k;
    rep(i, 0, n - 1) {
        int u, v; cin >> u >> v;
        grp[u].push_back(v);
        grp[v].push_back(u);
    }
    dfs(1, 0);
    sort(&dms[1], &dms[n + 1]);
    ll ans = 0;
    r_rep(i, n, k) ans += dms[i];
    cout << ans << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    //int tc; cin >> tc; while(tc--)
    solve();
    return 0;
}