CF1901E Compressed Tree（树dp）

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。