介绍

树形dp就是在树上进行dp，常用于 “树上选一组点/边，满足某些条件，且使得某些权值和最大” 的问题。

一般来说，DP的形式为：

设 dp[i][j] 为: 以 i 为根的子树当中，选了 j 个元素得到的最大值。

这样，状态转移就有：

dp[u][j]=maxto{dp[u][j−k]+dp[to][k]}

代码如下：

copy
1
2
3
4
5
for (int j = m; j >= 1; j--) {
    for (int k = 1; k <= j-1; k++) {
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

需要注意的点：

  1. 类似于 01 背包，在枚举 j 的值时，要从大到小，防止一个child被重复选择。
  2. 对于依赖关系（例如，child需要依赖parent），可以利用DP过程中，调整状态转移的 上下限 来达到！

时间复杂度：O(nm2)，其中 n 为节点数，m 为第二维的大小。

优化

子树 size 优化

对于一个子树，可能它第二维的上限并没有这么高，我们需要尽量避免枚举一些无用的范围。

我们可以优化一下：

对于每一个root节点 cur，我们记录一下 int sz[cur]，代表 以cur为根的子树的节点数量， 这样枚举的时候我们就可以优化成这样：

copy
1
2
3
4
5
for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
    for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

例题可见 例1

复杂度：O(nm)

DFS序 + 背包 优化

有的时候，第二维表示的不一定是 选择 j 个元素，而可能是背包的一个容量，此时上面的优化的效果就不显著了。

我们可以利用 DFS序 进行优化。

令 i 为 u 的DFS序编号，则对于当前节点 u，我们有两种选择：

  1. 选择当前节点：dp[i+1][j+wu]=max{dp[i][j]+vu}

  2. 不选当前节点：dp[i+szi][j]=max{dp[i][j]}

• 第一维度是选到了dfs序中的前 i 项，第二维度就是背包的容量。

解释：

如果选择当前节点，说明可以继续往子树里传递，所以传递到 dp[i+1][j+wu]。

如果不选择当前节点，由于依赖关系，就必须跳过子树，所以传递到 dp[i+szi][j]。

最终的答案就是 ans=maxj=0m{dp[n+1][j]}。

复杂度：O(nm)

例题可见 例2

例题

例1 洛谷P2014

题意

有 N 门课程，每门课程有 1 或 0 门前置课程，需要上了前置课程才能上这门课。每门课 i 有 si 学分。

现要选 M 门课，使得学分总和最大。

题解

设 dp[i][j] 为: 以 i 为根的子树当中，选了 j 个课程得到的最大值

根据前置课程的关系建图(会发现这是一棵树)，因为有前置课程，所以必须选了root才能选别的，故:

dp[i][1]=si

在处理某一个节点i的时候，dp[i][j] 代表的是： 以它为root的 “已探索” 子树中的最大值，所以在探索各个子树过程中有：

dp[cur][j]=max(dp[cur][j],dp[cur][k]+dp[nei][j−k]), k=[1,j−1]

实现细节

  1. 我们利用 dp[i][1]=si 来处理前置课程，是非常高效的做法！
  2. 状态转移的时候，要 倒序枚举 j， 也就是 j=m…1， 因为此时 dp[cur][k] 代表的是已探索的部分，不能包括 nei (因为 nei 正在被探索)。为了防止同一个 nei 被考虑多次，要倒序枚举！
  3. 给定的图可能是一个森林，所以创建一个超级root 0，并且将 M++ (因为 0 肯定要包含进去)，最终答案就是 dp[0][M+1]

算法优化

注意，在dp状态转移的时候，我们可能用的是如下loop:

copy
1
2
3
4
5
for (int j = m; j >= 1; j--) {
    for (int k = 1; k <= j-1; k++) {
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

每个节点 cur 都这样loop一次，总复杂度是 O(nm2)，看起来不可接受。

我们可以优化一下：

对于每一个root节点 cur，我们记录一下 int sz[cur]，代表 以cur为根的子树的节点数量， 这样枚举的时候我们就可以优化成这样：

copy
1
2
3
4
5
for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
    for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

时间复杂度：O(n2)

证明：我们考虑每一个 nei 被用来转移 的次数，会发现它只会在计算它的 parent 的dp值时才会被拿来统计，又因为每一个节点只有1个parent，所以每个节点对应的子树都只会被统计一次。

所以时间复杂度就是 T(∑i=1ni∗sz[i])=O(n2)

更严谨的数学证明可以参见 https://www.luogu.com.cn/blog/Chenxiao-Yan/solution-p4322

luogu-P2014-AC代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
const int maxm = 305;
int n,m;
int s[maxn];
int dp[maxn][maxn];
int sz[maxn];  //记录i的子树大小
struct Edge {
    int to, nxt;
} edges[maxm];
int head[maxn], ecnt = 1;
void add(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
void init() {
    scanf("%d%d",&n,&m);
    fill(head, head+n+2, -1);  //因为存在编号为0的节点，所以初始化为-1
    for (int i = 1; i <= n; i++) {
        int sc,k;
        scanf("%d%d",&k,&sc);
        s[i] = sc;
        add(k, i);
    }
}
void dfs(int cur, int par) {
    if (sz[cur]) return;  // visited
    dp[cur][1] = s[cur];
    sz[cur] = 1;
    for (int e = head[cur]; ~e; e = edges[e].nxt) {
        int nei = edges[e].to;
        if (par == nei) continue;
        dfs(nei, cur);
        sz[cur] += sz[nei];
        for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
            for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
                dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
            }
        }
    }
}
int main() {
    init();
    m++;
    dfs(0, -1);
    printf("%d\n", dp[0][m]);
}

如果每门课的前置课程不止1门，就不再是一棵树了，这样的话似乎可以用状压dp来解，leetcode某次比赛中出现过。

例2 洛谷P2515 [HAOI2010]软件安装

题意

给定 N 个软件，每个软件 i 要占用 Wi 的空间，价值为 Vi，并且每个软件 i 会依赖最多一个软件 Di。

如果要安装软件 i，必须要安装所有的直接/间接依赖软件。

电脑的空间为 M，求最大价值。

其中，1≤N≤100,0≤M≤500,0≤Wi≤M,0≤Vi≤1000,Di∈[0,N],Di≠i

题解

注意到，本题可能有 循环依赖。

对于循环依赖，直接用 SCC 缩点，剩下的就是一个标准的有依赖背包（本质上，树形DP）问题了：

如果 i 依赖 Di，那么将 Di 所在的 SCC 连一条有向边，指向 i 所在的 SCC 即可。

另外需要注意，本题可能是一个森林。所以缩点后，对于所有入度为 0 的点 u，需要用 0 连一条有向边指向 u。

最后，从 0 开始 DP 即可。

DP 的核心代码：

copy
1
2
3
4
5
6
7
8
9
10
11
void dfs(int u) {
    if (wei[u] <= m) dp[u][wei[u]] = val[u];
    for (int to : adj2[u]) {
        dfs(to);
        for (int i = m; i >= wei[u]; i--) {
            for (int j = wei[to]; j <= i - wei[u]; j++) {
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[to][j]);
            }
        }
    }
}

注意几点：

  1. dp[u][wei[u]] = val[u]; 放在最前面。
  2. DP的过程中，类似于 01 背包，i 是从大到小的，并且下限是 wei[u]。
  3. DP的过程中，j 的下限是 wei[to]，上限是 i - wei[u]（因为 i-j 的有效值必须 ≥ wei[u]）。

• 另外，别忘记 tarjan 过程中，更新 low[] 要判断是否在栈内。

树形DP（无优化版本）代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
int n, m, w[105], v[105], d[105];
int dp[103][503];
vector<int> adj1[103];
set<int> adj2[103];
int dfn[103], low[103], id = 0, st[103], tail = -1;
bool in[103];
int from[103], scc = 0;
void tarjan(int u) {
    in[u] = 1;
    st[++tail] = u;
    dfn[u] = low[u] = ++id;
    for (int to : adj1[u]) {
        if (!dfn[to]) {
            tarjan(to);
            low[u] = min(low[u], low[to]);
        } else if (in[to]) {  // 注意这里有 in[to]
            low[u] = min(low[u], dfn[to]);
        }
    }
    if (low[u] == dfn[u]) {
        from[u] = ++scc;
        while (tail >= 0 && st[tail] != u) {
            int cur = st[tail--];
            in[cur] = 0;
            from[cur] = scc;
        }
        tail--;
        in[u] = 0;
    }
}
void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        if (d[i] == 0) continue;
        adj1[d[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
}
int wei[103], val[103], ind[103];
void rebuild() {
    for (int i = 1; i <= n; i++) {
        int fu = from[i];
        wei[fu] += w[i];
        val[fu] += v[i];
        int fv = from[d[i]];
        if (fu == fv || fv == 0) continue;
        adj2[fv].insert(fu);
        ind[fu]++;
    }
    for (int i = 1; i <= scc; i++) {
        if (!ind[i]) adj2[0].insert(i);
    }
}
void dfs(int u) {
    if (wei[u] <= m) dp[u][wei[u]] = val[u];
    for (int to : adj2[u]) {
        dfs(to);
        for (int i = m; i >= wei[u]; i--) {  // 注意从大到小，注意下限
            for (int j = wei[to]; j <= i - wei[u]; j++) {  // 注意上下限
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[to][j]);
            }
        }
    }
}
int main() {
    init();
    rebuild();
    dfs(0);
    int ans = 0;
    for (int i = 0; i <= m; i++) ans = max(ans, dp[0][i]);
    cout << ans << endl;
}
DFS序 优化

我们可以利用 DFS序 进行优化，让时间复杂度从 O(nm2) 降到 O(nm)。

令 i 为 u 的DFS序编号，则对于当前节点 u，我们有两种选择：

  1. 选择当前节点：dp[i+1][j+wu]=max{dp[i][j]+vu}

  2. 不选当前节点：dp[i+szi][j]=max{dp[i][j]}

解释：

如果选择当前节点，说明可以继续往子树里传递，所以传递到 dp[i+1][j+wu]。

如果不选择当前节点，由于依赖关系，就必须跳过子树，所以传递到 dp[i+szi][j]。

最终的答案就是 ans=maxj=0m{dp[n+1][j]}。

另外需要注意，由于依赖问题，我们需要 记录每一个节点 u 的所有ancestor的权值和，在枚举的时候，将下限设置为这个权值和。（在代码中，pre[u] 代表 u 所有ancestor的权值和。）

优化代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 注意 idcnt = -1，因为我们是从 0 开始 DFS的！
int mp[103], idcnt = -1, sz[103];  // mp[i]: DFS序为 i 的节点编号 u
int pre[103];  // pre[u] 代表 u 的 ancestor 的 weight的和
void dfs(int u) {
    mp[++idcnt] = u;
    sz[u] = 1;
    for (int to : adj2[u]) {
        pre[to] = pre[u] + wei[u];  // ancestor的权值和
        dfs(to);
        sz[u] += sz[to];
    }
}
void solve() {
    for (int i = 1; i <= scc; i++) {
        int u = mp[i];
        for (int j = pre[u]; j <= m; j++) {  // 注意枚举下限从 pre[u] 开始
            dp[i+sz[u]][j] = max(dp[i+sz[u]][j], dp[i][j]);  // 不选
            if (j + wei[u] <= m)  // 选择（要保证 j+wei[u] <= m）
                dp[i+1][j+wei[u]] = max(dp[i+1][j+wei[u]], dp[i][j] + val[u]);
        }
    }
}
int main() {
    init();
    rebuild();
    dfs(0);
    solve();
    int ans = 0;
    for (int j = 0; j <= m; j++) ans = max(ans, dp[scc+1][j]);  // 注意是 scc+1
    cout << ans << endl;
}

例3 洛谷P4395 [BOI2003]Gem 气垫车

题意

给一棵 n 个节点的树，要求给所有节点标上正整数权值，使得相邻节点不能权值相同，求最小总权值。

其中，n≤104。

题解

第一眼看过去是个树染色问题，要么权值为 1，要么为 2。

很遗憾这个做法是错的，考虑一下这个数据，两个菊花接在一起：

img

这里很明显应该给 1,2 分别标上 2,3 的权值，其余全部标 1。

所以我们暴力枚举一下每个节点上可能标什么权值就好了，直觉上告诉我们这个上限不会太大。

然后利用树形DP来求最小值即可。

代码中取了上限 M=55，所以复杂度就是 O(552∗n)

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
const int M = 55;
struct Edge {
    int to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1, n, m;
int dp[maxn][M+3];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
void dfs(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, u);
        for (int j = 1; j <= M; j++) {
            int r = 1e9;
            for (int k = 1; k <= M; k++) {
                if (j == k) continue;
                r = min(r, dp[to][k]);
            }
            dp[u][j] += r;
        }
    }
    for (int j = 1; j <= M; j++) dp[u][j] += j;
}
int main() {
    fastio;
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1, 0);
    int ans = 1e9;
    for (int j = 1; j <= M; j++) ans = min(dp[1][j], ans);
    cout << ans << endl;
}

例4 洛谷P3177 [HAOI2015]树上染色

题意

给定一棵 n 个节点的树，树的边上有权值。

给定一个整数 k∈[0,n]，要求从树上选择 k 个点，将其染成黑色，剩余的染成白色。

染色后，获得的价值为 黑点两两之间的距离之和 + 白点两两之间的距离之和。

求最大价值？

其中，n,k≤2000。

题解

数据范围看起来就非常树形DP。

设 dp[u][i] 为在 u 的子树内，染 i 个黑点的总价值。

现在考虑一下怎么转移？

如果我们直接进行转移，就需要维护节点的深度之和，然而这很明显不现实，所以我们可以 考虑每条边 的贡献。

假设考虑的子树 v 中，染了 j 个黑点，那么一条边 (u,v,w) 的贡献刚好就是：

w∗(j∗(k−j)+(sz[to]−j)∗(n−k−sz[to]+j))

其中 j * (k-j) 是这条边两端的黑点数量的乘积，而 (sz[to] - j) * (n - k - sz[to] + j) 就是这条边两端的白点数量的乘积。

然后直接转移就可以了（注意第二维度的转移顺序是从 0 开始，否则会导致 dp[u][i] 被更新两次），注意一下使用 sz[] 进行时间复杂度优化到 O(n2)，否则是 O(n3)。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2003;
ll dp[maxn][maxn];
ll sz[maxn];
int n,k;
struct Edge {
    int to, nxt;
    ll w;
} edges[maxn<<1];
int ecnt = 1, head[maxn];
void addEdge(int u, int v, ll w) {
    Edge e = {v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
void dfs1(int u, int p) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        sz[u] += sz[to];
    }
}
void dfs(int u, int p) {
    dp[u][0] = dp[u][1] = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, u);
        ll w = edges[e].w;
        for (ll i = (ll)min((ll)k, sz[u]); i >= 0; i--) {   // u 用多少个黑
            for (ll j = 0; j <= min(i,sz[to]); j++) {  // v 用多少个黑
                ll cnt = j * (k - j) + (sz[to] - j) * (n - k - sz[to] + j);
                dp[u][i] = (ll)max(dp[u][i], dp[u][i-j] + dp[to][j] + cnt * w);
                // j = 0 开始: dp[u][i], dp[u][i-1] ... (正确)
                // j = min(i,sz[to]) 开始: dp[u][0], dp[u][1], ..., dp[u][i] -> 这导致 dp[u][i] 被更新了两次
            }
        }
    }
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n-1; i++) {
        int u,v; ll w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= k; j++) dp[i][j] = -1e18;
        
    dfs1(1, 0);
    dfs(1, 0);
    cout << dp[1][k] << endl;
}

注意事项

  1. 本题枚举 i,j 时，注意要加上 sz[u],sz[to] 作为上限来优化。
  2. 注意初始化 dp[i][j] 为负无穷，并且设 dp[i][0]=dp[i][1]=0。
  3. 注意第二维度的转移顺序（第一维倒序这个是必须的）。

例5 [1到n经过特定点的最短路]

题意

给定 n 个节点的一棵树，树上有 m 个点被标记了，求从节点 1 走到节点 n，中途需要经过这些标记点的最短路长度，所有边权值为 1。

其中，n≤2×105。

题解

• 这是一道群里传的题目，没有代码。

首先将 1 到 n 的路径拉成一条链，链上所有的点一定会被经过，不用管。

接下来就是挂在链上的若干子树，对于每个子树，思考如下问题：

从一棵树的根出发，经过树内的所有标记点，再回到这棵树的根，需要的最短路长度？

对于这个问题，我们考虑对于每个被标记的点 u，从根（假设为 1）到 u 的路径一定会被经过，被经过的这些边被打上标记，代表这些边一定会被经过。

打完标记后，我们知道在最优解中，每条边一定会被经过 2 次，所以答案就是标记边 ∗2。

如何打标记？

只要一次dfs即可，每次dfs时判断这个子树里面有没有需要标记的点，如果有，这条边就打上标记。

例6 NAQ2017E. Company Picnic

题意

给定一棵树，每个节点有权值 wi。

定义一组节点为：两个直接相连的节点 i,j，这组节点的权值定义为 min(wi,wj)。

求选出若干组节点的方法，使得每组节点用到的点各不相同，并且满足选出节点组数最多。

在节点组数量最多的情况下，求出这些节点的权值和最大值。

其中，2≤n≤1000,wi∈[2.2,5.3]。

题解

这个题需要维护最多节点组数，还要维护权值和最大值。所以 dp 数组维护两个值。

定义 dp(u,0) 为：u 的parent没有选它，dp(u,1) 则是选了它的。

dp 值则是一个pair：<int, double>，代表子树中最大的节点组数，以及对应的最大权值和。

在转移的时候，注意到 dp(u,1) 不能选任何 dp(v,1) 转移。而 dp(u,0) 只能选一个 dp(v,1) 转移（或者也可以不选）。

转移的过程中，优先更新第一个值（节点组数），如果第一个值相等，再更新第二个值（权值和最大值）。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+5;
pair<int,double> dp[maxn][2];
vector<string> adj[maxn];
map<string, int> mp;
double sp[maxn];
struct Edge {
    int to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
int rt;
void dfs(int u, int p) {
    int cnt = 0, b = 0;  // b: 最优转移 1 的点v
    double sum = 0;
    // 0 的情况
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs(v, u);
        cnt += dp[v][0].first;
        sum += dp[v][0].second;
        if (b == 0) b = v;
        else if (dp[v][1].first - dp[v][0].first > dp[b][1].first - dp[b][0].first) {
            b = v;
        } else if (dp[v][1].first - dp[v][0].first == dp[b][1].first - dp[b][0].first && 
            min(sp[u], sp[v]) + dp[v][1].second - dp[v][0].second > min(sp[u], sp[b]) + dp[b][1].second - dp[b][0].second) {
            b = v;
        }
        
    }
    if (!b) return;
    cnt -= dp[b][0].first;
    cnt += dp[b][1].first;
    sum -= dp[b][0].second;
    sum += min(sp[u], sp[b]) + dp[b][1].second;
    dp[u][0].first = cnt + 1;
    dp[u][0].second = sum;
    cnt = 0, sum = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        cnt += dp[v][0].first;
        sum += dp[v][0].second;
    }
    dp[u][1].first = cnt;
    dp[u][1].second = sum;
    if (cnt > dp[u][0].first || (cnt == dp[u][0].first && sum > dp[u][0].second)) {
        dp[u][0].first = cnt;
        dp[u][0].second = sum;
    }
}
int main() {
    fastio;
    int n; cin >> n;
    int id = 0;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (!mp.count(s) && s != "CEO") mp[s] = ++id;
        double w; cin >> w;
        string t; cin >> t;
        if (!mp.count(t) && t != "CEO") mp[t] = ++id;
        int u = mp[s], v = mp[t];
        if (t == "CEO") {
            rt = u;
        } else { 
            addEdge(u,v);
            addEdge(v,u);
        }
        sp[u] = w;
    }
    dfs(rt, -1);
    cout << dp[rt][0].first << " " << dp[rt][0].second / dp[rt][0].first << "\n";
}