题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$、$k(1 \leq k \leq 10^9)$、$c(1 \leq c \leq 10^9)$。

然后输入一棵无向树的$n-1$条边（节点编号从$1$开始），每条边的边权都是$k$。

树的根节点是$1$。每次操作，你可以花费$c$，把树的根节点改成其邻居之一。定义

• 树的的得分为其高度（根节点到最远叶子的距离）。
• 在计算最终得分时，要从树的得分中，扣除操作的总花费。

输出最终得分的最大值。

输入样例

4
3 2 3
2 1
3 1
5 4 1
2 1
4 2
5 4
3 4
6 5 3
4 1
6 1
2 6
5 1
3 2
10 6 4
1 3
1 9
9 7
7 6
6 4
9 2
2 8
8 5
5 10

输出样例

2
12
17
32

算法

换根DP

感觉没昨天那题难，甚至可以说容易很多，算是比较容易看出来的换根树形DP，因为题面中已经明确提到了换根操作。因此，先将根定为$1$，做一遍树形DP。然后再做一遍DFS进行换根，计算每个节点作为根时的得分，维护最大的得分。

树形DP

状态定义

$f[u]$表示以$u$为根的子树中，最远叶子节点到$u$的距离。

状态转移

设$v$为$u$的子节点，状态转移方程为$f[u]=k+max_{v}f[v]$。

在DFS过程中再处理出一个$depth$数组，$depth[u]$表示节点$u$的深度（深度是在根为$1$的情况下计算得到）。

DFS换根

然后跑$dfs(u,fa,vx)$换根，$fa$是$u$访问前最后一个访问的节点，防止走回头路。$vx$是$u$上面的所有节点到$u$的最大距离。初始情况下为$dfs(1,0,0)$，维护$max(vx,f[u])-depth[u] \times c$的最大值即可。

当从$u$转移到$v$时需要对$vx$进行更新，$v$上面节点到$v$的最长距离为$max(max_{v’}f[v’]+k,vx)+k$，其中$v’$是$v$以$u$为父节点的兄弟节点，它们要先走$k$的边权到$u$，然后从$u$上下来到$v$。为了快速求得$max_{v’}f[v’]+k$，需要对$u$的子节点做一个前后缀分解，维护子节点的前缀最大$f[v]+k$值和后缀最小$f[v]+k$值。

复杂度分析

时间复杂度

换根DP的本质就是对整棵树做两遍DFS，时间复杂度就是$O(n+m)$，$m$是边数，$n$是节点数，而数的边数$m=n-1$，所以时间复杂度为$O(n)$。

空间复杂度

树的邻接表空间为$O(n)$，DP数组$f$和高度数组$depth$都是线性空间$O(n)$，DFS的过程中最大递归深度也可能达到$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n;
vector<int> graph[N];
LL k, c, ans, f[N], depth[N];

LL dfs1(int u, int fa, LL d) {
    depth[u] = d;
    for(int v: graph[u]) {
        if(v == fa) continue;
        f[u] = max(f[u], k + dfs1(v, u, d + 1));
    }
    return f[u];
}

void dfs2(int u, int fa, LL vx) {
    ans = max(ans, max(f[u], vx) - depth[u]*c);
    vector<LL> child;
    for(int v: graph[u]) {
        if(v == fa) continue;
        child.push_back(f[v] + k);
    }
    int sz = child.size();
    vector<LL> pre(sz), suf(sz);
    for(int i = 0; i < sz; i++) {
        pre[i] = max(i? pre[i - 1]: 0, child[i]);
        int j = sz - 1 - i;
        suf[j] = max(j + 1 < sz? suf[j + 1]: 0, child[j]);
    }
    int i = 0;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs2(v, u, max(max(i? pre[i - 1]: 0, i + 1 < sz? suf[i + 1]: 0), vx) + k);
        i++;
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%lld%lld", &n, &k, &c);
        for(int i = 1; i <= n; i++) {
            graph[i].clear();
            f[i] = depth[i] = 0;
        }
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        ans = dfs1(1, 0, 0);
        dfs2(1, 0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}