我这道题的思路和网上都不太一样。
首先看一看这道题的性质吧。
这道题的决策还是比较复杂的
首先要选链，其次要选链上的点。然后找最大。
怎样处理信息来使得决策简化，这样DP转移就比较简洁且复杂度合理。
首先对于链上
可以看着这个美丽的图，我们考虑最大化差值，就要考虑差值的意义，
那么如果一个点被选，证明逃亡者来到了这个地方，后面的人一定也来，所以这个放置点的贡献为0,所有与这个点相连的点都有贡献，但是有特例，就是一个点被选，他在链上前一个点也被选，那么相当于这个点没有对逃亡者加贡献，而对于后面的人有贡献，因此总的贡献要加上这个点。
所以给出结论，考虑选点的话，选一个点代表不算自己的贡献，加上与这个所有相连的点的贡献，除了链上的上一个点。
这样只要定义f[i][j]为以1为起点的最长链，然后dfs的时候不算父亲（把父亲作为上一个点），就能写成一个及其简练的转移du表示之前说的x的贡献
然后可以$O(n)$枚举根，$O(nv)$DP,总复杂度$O(n^2v)$ 期望70pts
当然这个做法是可扩展的，就在于换根DP
然而取max是不能去除贡献的
所以要每次O(1)得到一个点取出某一儿子的贡献的dp值，可以把儿子拍到了一个序列，维护前缀max和后缀max，直接扫描儿子，就能得到去掉这个儿子的贡献。
其实可以维护前缀然后倒着扫。
然后调一个下午就可以AC了
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using std::cout; using std::endl; using std::max; using std::vector; const int N=100010,M=110; int fr[N],tt,n,m; long long f[N][M],du[N],a[N],tmp[N][M],ans=0; struct node{int to,pr;}mo[N*2]; inline int rd() { int s=0,w=1; char cc=getchar(); for(;cc<'0'||cc>'9';cc=getchar()) if(cc=='-') w=-1; for(;cc>='0'&&cc<='9';cc=getchar()) s=(s<<3)+(s<<1)+cc-'0'; return s*w; } void add(int x,int y) { mo[++tt]=(node){y,fr[x]}; fr[x]=tt; } void dfs1(int x,int fa) { for(int i=fr[x];i;i=mo[i].pr) { int to=mo[i].to; if(to==fa) continue; du[x]+=a[to]; dfs1(to,x); } for(int i=fr[x];i;i=mo[i].pr) { int to=mo[i].to; if(to==fa) continue; for(int j=1;j<=m;j++) f[x][j]=max(f[x][j],max(f[to][j-1]+du[x],f[to][j])); } } void dfs2(int x,int fa) { vector<long long>ve,sum[M]; for(int i=fr[x];i;i=mo[i].pr) { int to=mo[i].to; ve.push_back(to); for(int j=1;j<=m;j++) { f[x][j]=max(f[x][j],max(f[to][j-1]+du[x]+a[fa],f[to][j])),ans=max(ans,f[x][j]); //cout<<x<<" "<<j<<" "<<f[x][j]<<" "<<f[to][j-1]<<endl; f[x][j]=0; } } for(int j=0;j<=m;j++) { long long tp=0; for(int t=0;t<ve.size();t++) { int to=ve[t]; tp=max(tp,f[to][j]); sum[j].push_back(tp); } } for(int t=(int)ve.size()-1;t>0;t--) { int to=ve[t]; for(int j=m;j>=1;j--) { f[x][j]=max(f[x][j],max(max(tmp[x][j],tmp[x][j-1]+du[x]+a[fa]-a[to]),max(sum[j][t-1],sum[j-1][t-1]+du[x]+a[fa]-a[to]))); tmp[x][j]=max(tmp[x][j],f[to][j]); } if(to!=fa) dfs2(to,x); for(int j=1;j<=m;j++) f[x][j]=0; } if(ve.size()) { int to=ve[0]; for(int j=1;j<=m;j++) f[x][j]=max(f[x][j],max(tmp[x][j],tmp[x][j-1]+du[x]+a[fa]-a[to])); if(to!=fa) dfs2(to,x); //if(to!=fa)cout<<to<<" "<<j<<" "<<f[to][j]<<" "<<tmp[j&1^1]<<endl; } } int main() { //freopen("ex_chase2.in","r",stdin); n=rd();m=rd(); for(int i=1;i<=n;i++) a[i]=rd(); for(int i=1,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x); dfs1(1,0); dfs2(1,0); printf("%lld ",ans); } /* g++ 3.cpp -o 3 ./3 12 2 2 3 3 8 1 5 6 7 8 3 5 4 2 1 2 7 3 4 4 7 7 6 5 6 6 8 6 9 7 10 10 11 10 12 */