题解 P4657 [CEOI2017]Chase
zero4338
2021-07-21 08:10:52
## Solution
当我们固定一个起点后 , 把起点作为整个树的根 , 那么这时每个节点选不选的价值就是它所有儿子的铁球数量加和 .
那么设 $f_{i,j}$ 表示在 $i$ 子树里选择了 $j$ 个点所能得到的最大贡献 , 转移时考虑这个节点是否选择 .
设 $son_i$ 表示 $i$ 节点的儿子 , $v_i$ 表示 $i$ 节点的所有儿子铁球数量和 .
$f_{i,j}=\max(f_{son_i,j},f_{son_i,j-1}+v_i)$
枚举起点作为根 , 复杂度 $O(n^2v)$.
不能通过本题 ,
考虑沿用上面对价值的定义 , 设计新的 dp,
设 $f_{i,j,0/1},g_{i,j,0/1}$ 分别表示从 $i$($i$的子树)走到 $i$ 的子树($i$)中 , $i$ 被/不被)选 , 选了 $j$ 个的最大贡献 .
设当前节点为 $u$ , 儿子为 $son$, 父亲为 $fa$ , 当前节点儿子权值和为 $v$ , 点 $i$ 的铁球数量为 $p_i$.
那么有转移
$f_{u,j,0}=\max(f_{son,j,0},f_{son,j,1})$
$f_{u,j,1}=\max(\max(f_{son,j-1,0},f_{son,j-1,1})+v)$
$g_{u,j,0}=\max(g_{son,j,0},g_{son,j,1})$
$g_{u,j,1}=\max(\max(g_{son,j-1,0},g_{son,j-1,1})+v+p_{fa}-p_{son})$
注意路径方向的不同导致的价值变化 .
还要考虑 $u$ 自己作为起点 ,
即 $g_{u,1,1}=\max(v+p_{fa})$
但直接使用一个点的 $f$ 和 $g$ 去更新答案 , 无法保证路径不重复 ,
那么考虑在合并子树时更新答案 ,
$ans=\max(\max(f_{son,j,0},f_{son,j,1})+\max(g_{u,k,0},g_{u,k,1}))$
$ans=\max(\max(g_{son,j,0},g_{son,j,1})+\max(f_{u,k,0},f_{u,k,1}+p_{fa}-p_{son}))$
注意这里 $f,g$ 是由之前的全部儿子转移而来 , 所以能够保证路径不重复 .
注意由于 $f_{u,0,1},g_{u,0,1}$ 不合法 , 强制赋值负无穷 .
上式的 $j+k\leq v$ , 如果枚举 $j,k$ 会有 $O(v^2)$ 的复杂度 , 实际上只需维护前缀最大值就可做到 $O(v)$ 转移 .
时间复杂度 $O(nv)$
## Code
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define ll long long
using namespace std;
int read()
{
int ret=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
return ret;
}
const int maxn=1e5+5;
const int maxm=105;
const ll inf=1e15;
int n,v;
ll ans;
struct graph
{
int p[maxn];ll val[maxn];
int head[maxn],ver[maxn<<1],nxt[maxn<<1],tot;
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void link(int x,int y){add(x,y);add(y,x);}
ll f[maxn][maxm][2],g[maxn][maxm][2];
void dfs(int u,int fa)
{
val[u]=0;
for(int i=head[u];i;i=nxt[i])
{
if(ver[i]==fa)continue;
dfs(ver[i],u);val[u]+=p[ver[i]];
}
f[u][0][1]=g[u][0][1]=-inf;
g[u][1][1]=max(g[u][1][1],val[u]+p[fa]);
for(int i=head[u];i;i=nxt[i])
{
if(ver[i]==fa)continue;
ll mx1=0,mx2=0;
for(int j=v;j>=0;j--)
{
mx1=max(mx1,max(g[u][v-j][0],g[u][v-j][1]));
mx2=max(mx2,max(f[u][v-j][0],f[u][v-j][1]+p[fa]-p[ver[i]]));
ans=max(ans,max(f[ver[i]][j][0],f[ver[i]][j][1])+mx1);
ans=max(ans,max(g[ver[i]][j][0],g[ver[i]][j][1])+mx2);
}
for(int j=1;j<=v;j++)
f[u][j][0]=max(f[u][j][0],max(f[ver[i]][j][0],f[ver[i]][j][1])),f[u][j][1]=max(f[u][j][1],max(f[ver[i]][j-1][0],f[ver[i]][j-1][1])+val[u]);
for(int j=1;j<=v;j++)
g[u][j][0]=max(g[u][j][0],max(g[ver[i]][j][0],g[ver[i]][j][1])),g[u][j][1]=max(g[u][j][1],max(g[ver[i]][j-1][0],g[ver[i]][j-1][1])+val[u]+p[fa]-p[ver[i]]);
}
}
}o;
int main()
{
n=read();v=read();
for(int i=1;i<=n;i++)o.p[i]=read();
for(int i=1;i<=n-1;i++)o.link(read(),read());
o.dfs(1,0);
printf("%lld",ans);
return 0;
}
```