BOJ 15746 - Directory Traversal

BOJ 15746 - Directory Traversal

흔한 트리 DP를 이용한 re-rooting 문제일 것 같은데, 사실 맞다.

그런데 간선의 가중치가 부모에서 자식으로 가는것과 자식에서 부모로 가는것이 다르다.

부모에서 자식으로 가는 간선은 자식쪽 서브트리에 있는 파일의 개수에 자식의 파일 이름 길이 + 1 만큼 (filename/) 곱해져야 한다.

반대로는 3이 곱해져야 한다. ../

void solve() {
   int n;
   cin >> n;
   map<string, int> idx;
   vs names(n + 1);
   vvi edges(n + 1);
   vi is_file(n + 1);
   for (int i = 0; i < n; i++) {
      string name;
      cin >> name;
      names[i + 1] = name;
      int m;
      cin >> m;
      idx[name] = i + 1;
      if (m == 0) {
         is_file[i + 1] = 1;
      } else {
         while (m--) {
            int child;
            cin >> child;
            edges[i + 1].pb(child);
         }
      }
   }
   debug(edges);
   // i의 서브트리의 모든 파일들까지
   vi dp(n + 1), size(n + 1);
   function<void(int)> fn = [&](int cur) -> void {
      for (int to: edges[cur]) {
         if (is_file[to]) {
            size[cur]++;
            dp[cur] += sz(names[to]);
         } else {
            fn(to);
            size[cur] += size[to];
            dp[cur] += dp[to] + size[to] * (sz(names[to]) + 1); // folder3/
         }
      }
   };
   fn(1);
   int ans = 2e18;
   function<void(int)> dfs = [&](int cur) -> void {
      mina(ans, dp[cur]);
      for (int to: edges[cur]) {
         if (is_file[to]) {

         } else {
            int t = dp[to] + size[to] * (sz(names[to]) + 1);
            dp[cur] -= t;
            size[cur] -= size[to];
            dp[to] += dp[cur] + 3 * size[cur];
            size[to] += size[cur];
            dfs(to);
            size[to] -= size[cur];
            dp[to] -= dp[cur] + 3 * size[cur];
            size[cur] += size[to];
            dp[cur] += t;
         }
      }
   };
   dfs(1);
   cout << ans;
}