树覆盖型dp

遇到做过的题不会做，以后要好好改题 😦

\(\color{blue}\textbf{[例题]}\)
ZRtes AB day1 t3
2022syzx夏季训练4
poj#2152 fire

模型 #basic：

在树上选择若干个点，每个点能覆盖个离自己距离不大于某个值的所有点，问一系列最优化（计数不行）问题

设
f[i][j]表示目前已经做完了i的子树，且钦定i要么不被覆盖，要么被j覆盖的情况下
获得的最大最小值
best[i]表示某一个点的最优值
转移则考虑对于u枚举他被谁覆盖了，然后考虑如何去除多算的i的
费用，那么就有f[u][i]+=min\max(best[v],f[v][i]-w[i])，这
样就是相当于把给i的钱强制在树根u被计算，可能转移的时候发现
不连续，但是由于最优答案的性质，所以计算的答案被包含best里头
了因此不用分类讨论

//[zr AB day1 t3]
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch))f^=ch=='-',ch=getchar();while(isdigit(ch))x=x*10+(ch^48),ch=getchar();return f?x:-x;
}
const int N=1005,inf=1e18;
int dis[N][N],a[N],f[N][N],best[N],n,t,d,s;
vector<pair<int,int>> G[N];
void dfs1(int u,int fa,int rt){for(pair<int,int> v:G[u])if(v.first!=fa){dis[rt][v.first]=dis[rt][u]+v.second;dfs1(v.first,u,rt);}
}
void dfs2(int u,int fa){for(pair<int,int> v:G[u])if(v.first!=fa){dfs2(v.first,u);}for(int i=1;i<=n;++i){f[u][i]=(dis[u][i]<=d?a[u]:0)-s;for(pair<int,int> v:G[u])if(v.first!=fa){f[u][i]+=max(best[v.first],f[v.first][i]+s);}}for(int i=1;i<=n;++i){best[u]=max(best[u],f[u][i]);}
}		
signed main(){n=read(),t=read(),d=read(),s=read();for(int i=1;i<=n;++i)a[i]=read()*t;for(int i=1;i<n;++i){int x=read(),y=read(),z=read();G[x].push_back({y,z});G[y].push_back({x,z});}for(int i=1;i<=n;++i)dfs1(i,0,i);dfs2(1,0);printf("%lld\n",best[1]);return 0;
}

[fix]
关于best的作用：
其实发现定义的状态非常神奇：
每个点要么不被覆盖，要么强制被i覆盖，那么就会出现这种情况：
我钦定了u被很远的一个点控制，但是u的儿子v被很近的一个点控制
然后很远的这个点无法覆盖u，但是很近的这个点能够覆盖u，但是
由于我钦定了u被远点覆盖，因此在这种情况下没有贡献，并不合法
但是如果出现了这种情况，那么一定存在合法的状态比当前这个状态
的值更优，因此best里头就不会有这种非法的状态