【树形DP】CEOI2017 Chase

分析：

不算难的树形DP套路题。

首先，分析这个答案：可以视为，在一条路径上，选择了一些点，这些点的贡献为：
其周围的所有点权和 - 路径上一步的点权。

既然给出的是一颗树，所以可以把路径分为从下往上，从上往下两部分。

$DP[x][i][0/1]$表示，在x的子树中，到达x的路径，0表示从下往上走到这里，1表示从这里走到下面的最大贡献。

分为两部分主要是为了区分上一步的点是谁。（往下走的，上一步就是树里面的fa，往上走的，上一步就是树里面的son）

然后转移就分这个点用不用磁铁，比较简单，实在不会看代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
#define MAXV 110
using namespace std;
typedef long long ll;
ll dp[MAXN][MAXV][2];//0->go_up,1->go_down
vector<int> a[MAXN];
int n,V;
ll p[MAXN],sum[MAXN],ans;
ll getmax(ll &x,ll y){
    x=max(x,y);
}
void update(int x,int y,int fa){
    for(int i=1;i<V;i++)getmax(ans,dp[x][i][0]+dp[y][V-i][1]);//update the ans(...->u->x then x->v->...)for(int i=1;i<=V;i++){
    getmax(dp[x][i][0],max(dp[y][i][0],dp[y][i-1][0]+sum[x]-p[y]));//y->x,minus Pygetmax(dp[x][i][1],max(dp[y][i][1],dp[y][i-1][1]+sum[x]-p[fa]));//fa->x,minus Pfa}
}
void dfs(int x,int fa){
    for(int i=0;i<int(a[x].size());i++)if(a[x][i]!=fa)dfs(a[x][i],x);for(int i=1;i<=V;i++){
    dp[x][i][0]=sum[x];dp[x][i][1]=sum[x]-p[fa];	}for(int i=0;i<int(a[x].size());i++)update(x,a[x][i],fa);for(int i=1;i<=V;i++){
    dp[x][i][0]=sum[x];dp[x][i][1]=sum[x]-p[fa];	}for(int i=int(a[x].size())-1;i>=0;i--)//reverse it to avoid overlap (u -> x -> u)update(x,a[x][i],fa);	getmax(ans,max(dp[x][V][0],dp[x][V][1]));
}
int main(){
    SF("%d%d",&n,&V);int u,v;for(int i=1;i<=n;i++)SF("%d",&p[i]);for(int i=1;i<n;i++){
    SF("%d%d",&u,&v);	a[u].push_back(v);a[v].push_back(u);}for(int i=1;i<=n;i++)for(int j=0;j<int(a[i].size());j++)	sum[i]+=p[a[i][j]];dfs(1,0);PF("%lld",ans);
}