记录编号	583597	评测结果	AAWWWWEEEEEEEEEEEEEE
题目名称	3922.删除题目	最终得分	10
用户昵称	HzmQwQ	是否通过	未通过
代码语言	C++	运行时间	2.972 s
提交时间	2023-10-19 07:50:51	内存使用	9.93 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

#define MAXN 1005
#define INFL 0x3f3f3f3f3f3f3f3f
#define max(x, y) ((x) > (y) ? (x) : (y))

using namespace std;

typedef long long ll;

struct node {
    int to, wgt;
};

int n, son_sz[MAXN];
ll f[MAXN][MAXN];
vector <node> G[MAXN];

void dfs(int u) {
    son_sz[u] = 1;
    for(node nxt : G[u]) {
        int v = nxt.to;
        dfs(v);
        son_sz[u] += son_sz[v];
    }
    return ;
}

void dp(int u) {
    for(node nxt : G[u]) {
        int v = nxt.to;
        dp(v);
        for(int j = son_sz[u] - son_sz[v] + 1; j <= son_sz[u]; j++) f[u][j] = max(f[u][j], f[v][j - son_sz[u] + son_sz[v]]);
        for(int j = 1; j <= son_sz[v]; j++) f[u][son_sz[u] - son_sz[v]] = max(f[u][son_sz[u] - son_sz[v]], f[v][j] + (ll)j * (ll)(n - son_sz[v]) - (ll)nxt.wgt);
    }
    return ;
}

int main() {
    freopen("delete.in", "r", stdin);
    freopen("delete.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        int fa = 0, wfa = 0;
        scanf("%d %d", &fa, &wfa);
        G[fa].push_back((node){i, wfa});
    }
    dfs(1);
    dp(1);
    ll ans = 0LL;
    int sz1 = G[1].size();
    for(int i = 0; i < sz1; i++) {
        node nxt = G[1][i];
        int u = nxt.to;
        for(int j = 1; j <= son_sz[u]; j++) {
            for(int k = i + 1; k < sz1; k++) {
                node nxtk = G[1][k];
                int v = nxtk.to;
                int lsum_sz = n - son_sz[u] - son_sz[v];
                for(int l = 1; l <= son_sz[v]; l++) f[1][lsum_sz + j + l] = max(f[1][lsum_sz + j + l], f[u][j] + f[v][l]);
                for(int l = 1; l <= son_sz[v]; l++) f[1][lsum_sz + j] = max(f[1][lsum_sz + j], f[u][j] + f[v][l] + (ll)l * (ll)(lsum_sz + j) - (ll)nxtk.wgt);
            }
        }
        for(int j = 1; j <= son_sz[u]; j++) {
            for(int k = i + 1; k < sz1; k++) {
                node nxtk = G[1][k];
                int v = nxtk.to;
                int lsum_sz = n - son_sz[u] - son_sz[v];
                for(int l = 1; l <= son_sz[v]; l++) f[1][lsum_sz + l] = max(f[1][lsum_sz + l], f[u][j] + f[v][l] + (ll)j * (ll)(lsum_sz + l) - (ll)nxt.wgt);
                for(int l = 1; l <= son_sz[v]; l++) f[1][lsum_sz] = max(f[1][lsum_sz], f[u][j] + f[v][l] + (ll)j * (ll)(lsum_sz + l) + (ll)l * (ll)lsum_sz - (ll)nxtk.wgt - (ll)nxt.wgt);
            }
        }
    }
    for(int i = 0; i <= n; i++) ans = max(ans, f[1][i]);
    printf("%lld\n", ans);
    return 0;
}