SACO 2018 February Contest, Gold Problem 2. Directory Traversal

Original link: https://www.shuizilong.com/house/archives/saco-2018-february-contest-gold-problem-2-directory-traversal/

Basically Tree Distances II,

The transfer function is adjusted slightly.

  
   
#include <lastweapon/io>  
   
  
   
using namespace lastweapon;  
   
  
   
const int N = int(2e5) + 9;  
   
  
   
int n, m, h[N], c[N], l[N]; LL f[N], g[N];  
   
VVI v;  
   
  
   
void dfs1(int r, int p = -1) {  
   
    for(int& a : v[r]) if (a != p) {  
   
        dfs1(a, r);  
   
        h[r] += h[a];  
   
        f[r] += f[a] + h[a]*l[a];  
   
    }  
   
    if(!c[r]) h[r]++;  
   
}  
   
  
   
void dfs2(int r, int p = -1) {  
   
    for(int& a : v[r]) if (a != p) {  
   
        g[a] = (f[r] - (f[a] + h[a]*l[a])) + g[r] + (m - h[a])*3;  
   
        dfs2(a, r);  
   
    }  
   
}  
   
  
   
int main() {  
   
  
   
  
   
freopen("dirtraverse.in", "r", stdin);  
   
freopen("dirtraverse.out", "w", stdout);  
   
  
   
  
   
    RD(n);  
   
    v. resize(n);  
   
    int a;  
   
    string s;  
   
    REP(i, n) {  
   
        cin >> s;  
   
        l[i] = s. size();  
   
        RD(c[i]);  
   
        if(c[i]) l[i]++;  
   
        else m++;  
   
        REP(j, c[i]) {  
   
            RD(a), a--;  
   
            v[i].PB(a);  
   
            v[a].PB(i);  
   
        }  
   
    }  
   
    dfs1(0);  
   
    dfs2(0);  
   
    LL ans = INFF;  
   
    REP(i, n) ans = min(ans, f[i]+g[i]);  
   
    cout << ans << endl;  
   
}  
   
  
   

This article is reproduced from: https://www.shuizilong.com/house/archives/saco-2018-february-contest-gold-problem-2-directory-traversal/
This site is only for collection, and the copyright belongs to the original author.