Problem
Solution
来自fcy大佬的思路
记 \(f_u\) 表示假定以 \(u\) 为根的子树，在压缩后，（子树内的某一个点（包括 \(u\)））可以向外（除\(u\)为根的子树外所以点的集合）连一条边时的最大 \(sum\)。换言之，我们把树拆成 以\(u\)为根的子树（记作 \(Tree_u\)） 和 非 \(Tree_u\) 部分。而且，假定 \(Tree_u\) 部分在压缩后一定有向外的边（可以是 \(u\) 连出去的，也可以是 \(u\) 被压缩后 \(u\) 子树内的某一个点连出去的）,连向非 \(Tree_u\) 部分。
假设当前结点为 \(u\) ，考虑 \(f_u\) 的状态转移，记 \(u\) 的儿子为 \(v_1,v_2,...,v_m\)，那么有三种转移情况：一、取0个儿子，\(a_u\) 就是 \(f_u\)；二、取1个儿子，那么 \(u\) 会被压缩， \(a_u\) 不加入 \(f_u\) 的计算；三、取2个或2个以上的儿子，\(u\) 不会被压缩，\(a_u\) 要加入 \(f_u\) 的计算中。
考虑答案的计算。假定 \(1\) 为根，此时，根不能向外连边，这是与 \(f_u\) 的定义不同的。但是，我们可以仿照 \(f_u\) 的状态转移来计算答案。具体的，分为 种：一、取0个儿子，此时 \(a_1\) 就是答案；二、取1个儿子，\(1\) 是“叶子”结点，\(a_1\) 加入到答案的计算；三、取2个儿子，\(1\) 会被压缩，\(a_1\) 不加入答案的计算；四、取2个以上的儿子，\(1\) 不会被压缩，\(a_1\) 加入答案的计算。
考虑到 \(f_u\) 的意义，\(Tree_u\) 在压缩后可以向 非 \(Tree_u\) 部分 连边当且仅当 非 \(Tree_u\) 部分 不为空集。因此 \(1\) 为根已经考虑任意 \(u\) 的 非 \(Tree_u\) 部分 不为空集的答案。因此，剩余未考虑的答案 有且仅有 对于任意 \(u\)，非 \(Tree_u\) 部分 为空集的答案。事实上，对于任意 \(u\)，像 \(1\) 一样计算答案即可（相当于把 \(Tree_u\) 当成“整棵树”）。
最后的 \(\max\) 便是答案
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int INF = 1e18;
const int N = 5e5+7;
int n,cnt;
int a[N],head[N],f[N];
struct Edge {
int next, to;
}edge[N<<1];
void add(int u,int v) {
edge[++cnt] = (Edge)<%head[u], v%>;
head[u] = cnt;
}
bool cmp(int x, int y) {
return x > y;
}
int ans;
void Dfs(int u,int fa) {
f[u] = a[u], ans = max(ans, a[u]);
vector<int> son;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
if(v == fa) continue;
Dfs(v, u), son.emplace_back(f[v]);
}
if(!son.size()) return ;
sort(son.begin(), son.end(), cmp);
f[u] = max(f[u], son[0]);
int sum = son[0];
for(int i=1;i<son.size();++i) {
sum += son[i];
f[u] = max(f[u], sum+a[u]);
if(son[i] <= 0) break;
}
if(son.size() >= 1) ans = max(ans, son[0]+a[u]);
if(son.size() >= 2) ans = max(ans, son[0]+son[1]);
if(son.size() > 2) {
sum = son[0] + son[1];
for(int i=2;i<son.size();++i) {
sum += son[i];
ans = max(ans, sum+a[u]);
if(son[i] <= 0) break;
}
}
}
void solve() {
n = read();
for(int i=1;i<=n;++i) a[i] = read();
for(int i=1;i<n;++i) {
int x = read(), y = read();
add(x, y), add(y, x);
}
ans = 0;
Dfs(1, 0);
printf("%lld\n",ans);
for(int i=1;i<=n;++i) a[i] = head[i] = f[i] = 0;
cnt = 0;
}
signed main()
{
int T = read();
while(T--) {
solve();
}
return 0;
}
Summary
有时候题目哪里限制我们让我们不好dp，我们就假定一个条件让它好dp。