基本就是 Tree Distances II，
转移函数稍微调整下。

#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;
}

Posted by xiaodao
Category: 日常