被这个东西薄纱了。
顾名思义，树上的动态规划即树形动态规划。
P1352 没有上司的舞会
经典题！
设 \(f_{i,0 / 1}\) 表示第 \(i\) 个节点，选或不选自己的最优情况。
显然有方程 \(f_{i,0}=\sum \max\{f_{j,0},f_{j,1}\}\) 和 \(f_{i,1}=\sum f_{j,0}\)。
即：不选这个点时，它的子节点选不选都行；选这个点时，他的子节点都不能选。
#include <stdio.h>
using namespace std;
inline int max(const int &_x,const int &_y){
return _x>_y?_x:_y;
}
int i,n,x,y,ans;
int dp[6005][2];
int main(){
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",dp[i]+1);
ans=dp[1][1];
for(i=1;i<n;++i){
scanf("%d %d",&x,&y);
if((dp[y][1]+=dp[x][0])>ans)
ans=dp[y][1];
if((dp[y][0]+=max(dp[x][0],dp[x][1]))>ans)
ans=dp[y][0];
}
printf("%d",ans);
return 0;
}
P4084 [USACO17DEC]Barn Painting G
设 \(f_{i,0/1/2}\) 表示节点 \(i\) 染色成 \(0/1/2\) 时以它为根的子树方案数。
如果 \(c_i\not = -1\)，即这个点颜色是确定的，那么其他两个颜色的 \(f_{i,color}\) 均为 \(0\)。
其余情况 \(f_{i,color}=1\)。
容易推出方程：
- \(f_{i,0}=\prod (f_{j,1}+f_{j,2})\)
- \(f_{i,1}=\prod (f_{j,0}+f_{j,2})\)
- \(f_{i,2}=\prod (f_{j,0}+f_{j,1})\)
记得取模。
#include <vector>
#include <stdio.h>
std::vector<int> e[100005];
int col[100005];
int pos[100005];
long long f[100005][5];
const int mod=1000000007;
inline void dfs(int id,int fa)
{
if(col[id])
{
f[id][pos[id]]=1;
}else
{
f[id][0]=
f[id][1]=
f[id][2]=1;
}
for(auto nxt:e[id])
{
if(nxt==fa)
continue;
dfs(nxt,id);
(f[id][0]*=f[nxt][1]+f[nxt][2])%=mod;
(f[id][1]*=f[nxt][0]+f[nxt][2])%=mod;
(f[id][2]*=f[nxt][0]+f[nxt][1])%=mod;
}
// printf("%d %d %d %d\n",id,f[id][0],f[id][1],f[id][2]);
return ;
}
int main()
{
int n,k,i,u,v;scanf("%d %d",&n,&k);
for(i=1;i<n;++i)
{
scanf("%d %d",&u,&v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for(i=1;i<=k;++i)
{
scanf("%d %d",&u,&v);
col[u]=true;
pos[u]=v-1;
}
dfs(1,0);
printf("%lld",(f[1][0]+f[1][1]+f[1][2])%mod);
}
P3047 [USACO12FEB]Nearby C
强大的题目。
看数据范围显然想到算法大概是 \(O(nk)\sim O(nk^2)\) 。
直接冲 \(O(nk)\)。
设 \(g_{i,dis}\) 表示从节点 \(i\) 向下走 \(dis\) 个点以内的点权和。
显然 \(g_{i,dis}=c_i+\sum d_{j,dis-1} \mid j\in son_i\)。
我们输出 \(g\) 数组肯定不对，所以我们再设 \(f_{i,dis}\) 表示节点 \(i\) 周围 \(dis\) 个节点的点权和。
推出式子：\(f_{i,dis}=f_{father_i,j-1}-g_{i,dis-2}+g_{i,dis}\)。
-
\(f_{father_i,j-1}\) 是从 \(i\) 上 \(dis\) 级祖先到 \(dis-2\) 级子孙。
-
\(g_{i,dis-2}\) 是从 \(i\) 到 \(dis-2\) 级子孙。
-
\(g_{i,dis}\) 是 从 \(i\) 到 \(dis\) 级子孙。
- 不难发现，这样计算出来的一定是 \(k\) 级祖先到 \(k\) 级子孙。
#include <vector>
#include <stdio.h>
std::vector<int> e[100005];
int c[100005],f[100005][25],g[100005][25];
inline void dfs(int id,int fa,int dis)
{
g[id][dis]=c[id];
for(auto nxt:e[id])
{
if(nxt==fa)
continue;
g[id][dis]+=g[nxt][dis-1];
dfs(nxt,id,dis);
}
return ;
}
inline void pre(int id,int fa,int dis)
{
f[id][dis]=f[fa][dis-1]-(dis>=2?g[id][dis-2]:0)+g[id][dis];
for(auto nxt:e[id])
{
if(nxt!=fa)
pre(nxt,id,dis);
}
}
inline void solve(int dis)
{
for(auto nxt:e[1])
{
pre(nxt,1,dis);
}
}
int main()
{
int n,k,u,v,dis,i;scanf("%d %d",&n,&k);
for(i=1;i<n;++i)
{
scanf("%d %d",&u,&v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for(i=1;i<=n;++i)
{
scanf("%d",c+i);
f[i][0]=g[i][0]=c[i];
}
for(dis=1;dis<=k;++dis)
{
dfs(1,0,dis);
f[1][dis]=g[1][dis];
}
/* for(i=1;i<=n;++i)
{
for(int j=0;j<=k;++j)
printf("%d ",g[i][j]);
puts("");
}*/
for(i=1;i<=k;++i)
{
solve(i);
}
for(i=1;i<=n;++i)
{
printf("%d\n",f[i][k]);
}
}
[ABC259F] Select Edges
甜橙好闪，拜谢甜橙。
感觉属于比较套路的题，设 \(f_{i,0/1}\) 表示没有/有向父亲的连边（这样设是为了方便转移。）
- \(f_{i,0}=\sum (f_{u_k,1}+\omega(i,u_k))\)，\(k\le d_i\)。
- \(f_{i,1}=\sum (f_{u_k,1}+\omega(i,u_k))\)，\(k< d_i\)。
然后先向下搜，回溯时转移。
#include <map>
#include <vector>
#include <stdio.h>
#include <algorithm>
std::vector<std::pair<int,int>>e[300005];
int n;
int d[300005];
long long f[300005][2];
void solve(int u,int fa)
{
int i,v,w;
long long sum=0;
std::vector<long long> val;
for(auto nxt : e[u])
{
v=nxt.first;w=nxt.second;
if(v==fa)
continue;
solve(v,u);
sum+=f[v][0];
val.emplace_back(f[v][1]-f[v][0]+w);//减掉 f[v][0] 是下面加回来的。
}
sort(val.begin(),val.end(),std::greater<long long>());
for(i=0;i<std::min((int)val.size(),d[u]-1);i++)
sum+=std::max(0ll,val[i]);
f[u][0]=sum;
if(val.size()>d[u]-1)
f[u][0]+=std::max(0ll,val[d[u]-1]);
if(!d[u])
f[u][1]=-(1ll<<60);
else
f[u][1]=sum;
return ;
}
int main()
{
int n,i,u,v,w;
scanf("%d ",&n);
for (i=1;i<=n;++i)
scanf("%d",d+i);
for (i=1;i<n;++i)
{
scanf("%d %d %d",&u,&v,&w);
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
solve(1,0);
printf("%lld",std::max(f[1][0],f[1][1]));
}
[ABC248G] GCD cost on the tree
想了快半小时，除了暴力毫无思路！
所以此处丢个友情衔接就咕咕咕了！
P8564 ρars/ey
树上背包典中典！
由于我现在不大能看懂以前神秘的代码风格所以解释就咕咕咕了捏。/tiao
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int head[5005],to[200005],nex[200005],top=0;
long long f[5005][5005],v[5005];
const long long INF=1ll<<60;
int n;
int cnt[5005];
bool vis[5005];
void dfs(int x){
vis[x]=true;
for(int i=head[x];~i;i=nex[i])
if(!vis[to[i]]){dfs(to[i]);cnt[x]+=cnt[to[i]];}
return;
}
void solve(int x){
int count_x,count_y,i,j,k;
count_x=count_y=0;
vis[x]=true;
for(i=1;i<cnt[x];i++)f[x][i]=INF;
f[x][1]=0;
for(i=head[x];~i;i=nex[i]){
if(!vis[to[i]]){
solve(to[i]);
for(j=count_y+1;j>=count_x+1;--j){
for(k=1;k<=cnt[to[i]];k++)
f[x][k+j]=min(f[x][k+j],f[x][j]+f[to[i]][k]);
f[x][j]=INF;
}
count_x++;
count_y+=cnt[to[i]];
for(j=count_x;j>=1;j--)f[x][j]=INF;
}
}
f[x][1]=v[cnt[x]];
for(i=count_x+1;i<=cnt[x];++i)
f[x][1]=min(f[x][1],f[x][i]+v[i]);
return;
}
inline void add(int u,int v){
to[++top]=v;
nex[top]=head[u];
head[u]=top;
return;
}
int main() {
// freopen("parsey.in","r",stdin);
// freopen("parsey.out","w",stdout);
int n,x,y;
scanf("%d",&n);
memset(head,-1,sizeof head);
for (int i=2; i<=n; i++) scanf("%lld",&v[i]);
for (int i=1; i<=n; i++) cnt[i]=1;
for (int i=1; i<n; i++) {
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1);
memset(vis,false,sizeof(vis));
solve(1);
printf("%lld",f[1][1]);
return 0;
}
P3360 偷天换日
输入格式极其的锶麻麻。
看懂了之后就是二叉树，二叉树采用 \(i\to i\times 2,i\times 2+1\) 的形式存储。开四倍空间（同线段树）。
剩下的就是背包，背包都不会可以回去采药。
#include <stdio.h>
#include <algorithm>
#define lc(id) (id<<1)
#define rc(id) (id<<1|1)
int n,f[3005][1005];
inline void solve(int id){
int t,x,i,j,w,c;
scanf("%d %d",&t,&x);
t<<=1;
if(x>0){
for(i=1;i<=x;i++)
{
scanf("%d %d",&w,&c);
for(j=n;j>=t+c;--j)
f[id][j]=std::max(f[id][j],f[id][j-c]+w);
}
}else
{
solve(lc(id));
solve(rc(id));
for(i=n;i>=t;--i)
for(j=0;j+t<=i;++j)
f[id][i]=std::max(f[id][i],f[lc(id)][j]+f[rc(id)][i-j-t]);
}
}
int main()
{
scanf("%d",&n);--n;
solve(1);
printf("%d",f[1][n]);
return 0;
}
CF1083A The Fair Nut and the Best Path
简单题，直接搜搜搜，感谢良心出题人！
#include <map>
#include <vector>
#include <stdio.h>
#include <algorithm>
std::vector<std::pair<int,int>>e[300005];
long long f[300005];
long long ret(-1);
int i,n,u,v,w;
int val[300005];
inline void dfs(int id,int fa)
{
int i,j,k;
f[id]=val[id];
ret=std::max(ret,f[id]);
for(auto [nxt,w]:e[id])
{
if(nxt!=fa)
{
dfs(nxt,id);
ret=std::max(ret,f[id]+f[nxt]-w);
f[id]=std::max(f[id],val[id]+f[nxt]-w);
}
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",val+i);
for(i=1;i<n;++i)
{
scanf("%d %d %d",&u,&v,&w);
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
dfs(1,0);
printf("%lld",ret);
return 0;
}