题目概述

有 $n$ 个点的树，每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走，有 $k$ 次放面包的机会，放下面包后相邻点的咕咕咕就会凑到该点，问先走一遍之后再走一遍遇到的咕咕咕个数之差最大是多少。

解题报告

考虑已知从哪个点出发，那么每个点放不放面包的贡献是固定的，与上一个点有没有放面包无关（上一个点放面包这个点再来一次又凑过来了……），所以 $O(n^2log_k)$ 贪心很显然。

不过这个很像求直径啊，考虑树形DP。由于有方向所以记录 $f[i][j]$ 表示向上走到 $i$ ，放了 $j$ 次面包，再记录 $g[i][j]$ 表示向下走到 $i$ ，放了 $j$ 次面包。

树形DP很容易写丑……Orz%%%KCZ，写的超级简洁。大概就是每个点儿子正着做一遍，反着做一遍（因为路径有方向，所以要正反都做）。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=100;

int n,m,a[maxn+5];LL sum[maxn+5],f[maxn+5][maxm+5],g[maxn+5][maxm+5],ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],now[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void DP(int x,int y,int pre){
    for (int j=0;j<=m;j++) ans=max(ans,f[x][j]+g[y][m-j]);
    for (int j=1;j<=m;j++) f[x][j]=max(f[x][j],max(f[y][j],f[y][j-1]+sum[x]-a[y]));
    for (int j=1;j<=m;j++) g[x][j]=max(g[x][j],max(g[y][j],g[y][j-1]+sum[x]-a[pre]));
}
void Dfs(int x,int pre=0){
    memset(f[x],0,sizeof(f[x]));memset(g[x],0,sizeof(g[x]));f[x][1]=sum[x];g[x][1]=sum[x]-a[pre];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x),DP(x,son[j],pre);
    ans=max(ans,max(f[x][m],g[x][m]));now[0]=0;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) now[++now[0]]=son[j];
    memset(f[x],0,sizeof(f[x]));memset(g[x],0,sizeof(g[x]));f[x][1]=sum[x];g[x][1]=sum[x]-a[pre];
    for (int i=now[0];i;i--) DP(x,now[i],pre);ans=max(ans,max(f[x][m],g[x][m]));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),sum[x]+=a[y],sum[y]+=a[x],Add(x,y),Add(y,x);
    Dfs(1);return printf("%lld\n",ans),0;
}