一种和其他题解不同的dp定义
发现其他题解是四倍空间 选和不选 最大次大
因为比较恶心 所以我们考虑直接强制这个点不选
当其他点dp到它时再考虑它自己
码量很小 也简洁易懂
注意当\(i\)的值由\(i-1\)的值转移过来时还要判断\(i-1\)的值是用最大值转移还是次大值转移
换根一共四种情况
设可以用来更新的值为\(tmp\) 选上父节点的贡献为\(res\)
1 \(tmp=max(f[fa[u]][i],f[fa[u]][i−1]+res)\)（\(i\)处最大值 \(i-1\)处最大值都不来源于\(u\)）
2 \(tmp=max(f[fa[u]][i],g[fa[u]][i−1]+res)\)（剩下三种同理）
3 \(tmp=max(g[fa[u]][i],f[fa[u]][i−1]+res)\)
4 \(tmp2=max(g[fa[u]][i],g[fa[u]][i−1]+res)\)
注意特判\(0\)下标 否则\(i-1\)会访问负下标
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define Sakura int
#define Re register ll
#define _ putchar(' ')
#define el putchar('\n')
#define ll long long
using namespace std;
const ll maxn=1e5+10;
inline ll read(){
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
vector<ll> G[maxn];
ll n,m;
ll a[maxn];
ll f[maxn][110],g[maxn][110];
ll tmp1[110];
ll fa[maxn];
ll sum[maxn];
ll ans;
void dfs1(ll u){
for(auto v:G[u]){
if(v==fa[u]) continue;
fa[v]=u;
sum[u]+=a[v];
dfs1(v);
for(Re i=1;i<=m;++i){
ll tmp=max(f[v][i],f[v][i-1]+sum[v]);
if(tmp>=f[u][i]){
g[u][i]=f[u][i];
f[u][i]=tmp;
}
else g[u][i]=max(g[u][i],tmp);
}
}
}
void dfs2(ll u){
if(fa[u]){
ll res=sum[fa[u]]-a[u]+a[fa[fa[u]]];
for(Re i=1;i<=m;++i) tmp1[i]=max(f[u][i],f[u][i-1]+sum[u]);
for(Re i=1;i<=m;++i){
ll tmp2;
if(g[fa[u]][i]>=tmp1[i])
if(g[fa[u]][i-1]>=tmp1[i-1]) tmp2=max(f[fa[u]][i],f[fa[u]][i-1]+res);
else tmp2=max(f[fa[u]][i],g[fa[u]][i-1]+res);
else
if(g[fa[u]][i-1]>=tmp1[i-1]) tmp2=max(g[fa[u]][i],f[fa[u]][i-1]+res);
else tmp2=max(g[fa[u]][i],g[fa[u]][i-1]+res);
if(tmp2>=f[u][i]){
g[u][i]=f[u][i];
f[u][i]=tmp2;
}
else g[u][i]=max(g[u][i],tmp2);
}
}
ans=max(ans,max(f[u][m],f[u][m-1]+sum[u]+a[fa[u]]));
for(auto v:G[u]) if(v!=fa[u]) dfs2(v);
}
Sakura main(){
n=read(),m=read();
if(!m){
puts("0");
return 0;
}
for(Re i=1;i<=n;++i) a[i]=read();
for(Re i=1;i<n;++i){
ll x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(1);
dfs2(1);
ot(ans);
}