题目描述

难度分:$2600$

输入$n(2 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，表示每个节点的点权。

然后输入一棵树的$n-1$条边，节点编号从$1$开始。

从这棵树中，选出两条不相交的路径，也就是没有节点会同时出现在两条路径中。输出这两条路径的节点点权之和的最大值。

输入样例$1$

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

输出样例$1$

25

输入样例$2$

2
20 10
1 2

输出样例$2$

30

算法

树形DP

这个状态定义和转移也太复杂了，又是学习的一天。用$w[u]$表示节点$u$的点权。

状态定义

$f[u][0]$表示以$u$为根的子树中，两条不相交链的最大点权和。$f[u][1]$表示以$u$为根的子树中，点权和最大的一条链。$g[u]$表示以$u$为根的子树中，$u$到叶子节点+另外一条链的最大点权和。$h[u]$表示以$u$为根的子树中，$u$的儿子节点$son$中$f[son][1]$的最大值，这个$h$主要就是用来保证两条链不相交。$down[u]$表示从$u$到叶子节点的最大点权和。

对此无根树随便定一个根节点$1$，则在这个状态定义下，答案就应该是$f[1][0]$。

状态转移

对于某个节点$u$，$f[u][0]$的转移来源有：

1. $f[v][0]$，其中$v$是$u$的一个子节点，这表示直接继承$v$子树的答案。
2. $f[u][1]+f[v][1]$，表示从子树$u$中点权和最大的链+子树$v$中点权和最大的链。
3. $down[u]+g[v]$，表示子树$v$内到叶子节点的链往上延伸穿过节点$u$形成的一条链+子树$v$中一条与之不相交的链。
4. $down[v]+g[u]$，与上一个转移类似，表示子树$v$到某个叶子节点的链往上延伸穿过节点$u$形成一条链+子树$u$中一条与之不相交的链。

以上$4$种情况选较大的转移。

$g[u]$的转移来源有：

1. $w[u]+g[v]$，表示直接将叶子节点到$v$的链延伸到$u$形成一条链+子树$v$中一条与之不相交的链。
2. $down[u]+f[v][1]$，表示子树$v$中点权和最大的一条链+子树$u$中从$u$到叶子节点点权和最大的一条链（两条链不相交，因为此时$down[u]$还没有更新完全，只有$v$节点的信息是全的，得不到$u$穿过$v$达到某个叶子节点的路径信息）。
3. $down[v]+w[u]+h[u]$，表示让$v$到某个叶子节点的路径往上延伸到$u$+$u$的子节点子树中最大点权和的那条链。

以上$3$种情况选较大的转移。

$h[u]$比较好维护，在遍历子节点$v$时维护就行，$h[u]=max_{v}f[v][1]$。

$down[u]$同理，在遍历子节点$v$时维护，$down[u]=max_{v}down[v]+w[u]$。

复杂度分析

时间复杂度

状态数量是$O(n)$（准确来说是$4n$），单次转移的时间复杂度为$O(1)$。整个算法的时间复杂度就是遍历一遍树的时间复杂度，因为树的边也是$O(n)$级别（准确来说是$n-1$），所以时间复杂度为$O(n)$。

空间复杂度

除了输入的点权数组$w$，树的邻接表空间复杂度为$O(n+m)$，其中$m$是边数，由于是树所以$m=n-1$，邻接表的空间复杂度为$O(n)$。DP数组的空间复杂度为$O(4n)=O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010, INF = 0x3f3f3f3f;
int n, w[N];
vector<int> graph[N];
LL f[N][2], g[N], h[N], down[N];

void dfs(int u, int fa) {   
    f[u][0] = f[u][1] = g[u] = down[u] = w[u];  
    h[u] = 0;   
    for(int v: graph[u]) {      
        if(v == fa) continue;   
        dfs(v, u);
        f[u][0] = max(f[u][0], f[v][0]);
        f[u][0] = max(f[u][0], f[u][1] + f[v][1]);
        f[u][0] = max(f[u][0], down[u] + g[v]); 
        f[u][0] = max(f[u][0], g[u] + down[v]);
        f[u][1] = max(f[u][1], f[v][1]);
        f[u][1] = max(f[u][1], down[u] + down[v]);
        g[u] = max(g[u], w[u] + g[v]);
        g[u] = max(g[u], down[u] + f[v][1]);    
        g[u] = max(g[u], down[v] + w[u] + h[u]);
        h[u] = max(h[u], f[v][1]);
        down[u] = max(down[u], down[v] + w[u]);
    }
}

int main() {    
    scanf("%d", &n);    
    for(int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        graph[i].clear();
    }
    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);
    }
    dfs(1, 0);
    printf("%lld\n", f[1][0]);
    return 0;
}