主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
树形dp
最后更新于 2025-06-15 17:13:07
作者
asuldb
分类
个人记录
复制 Markdown
查看原文
更新内容
好说好久没写树形dp了，今天切掉三道水题，干脆就把以前写的总结搬过来吧 ## 1.子树和类 ### CF767C Garland [http://codeforces.com/problemset/problem/767/C](题目) 很神的一道题，题目大意是把一棵树切成三份，使每一份的子树和相等 结果就瞎写一气在cf上面向数据编程 到了几个数据点大到无法显示的时候，怎么魔改也是wa 那么只好面向题解编程 再看了题解之后才发现这种题是有套路的： 当我们通过dfs处理子树和的时候我们就可以进行操作了，毕竟这是递归的，所以当一棵子树的子树和已经被处理好且它的子树和恰好为整个树权值的三分之一时 那么好了我们就可以在这里切一刀，同时把这棵子树的权值改成0，表示这棵子树已经被切了下来，这样我们就可以继续去进行上面的操作了 ```cpp ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 3000001 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int n,sum[maxn],num,S; int root,max_deep; int w[maxn],head[maxn],deep[maxn],ans[3],tot; bool flag=1; inline int read() { char c=getchar(); int x=0,r=1; while(c<'0'||c>'9') { if(c=='-') r=-1; c=getchar(); } while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*r; } inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline void build(int r) { sum[r]+=w[r]; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { max_deep=max(max_deep,deep[e[i].v]+1); deep[e[i].v]=deep[r]+1; build(e[i].v); sum[r]+=sum[e[i].v]; } if(sum[r]==S) ans[++tot]=r,sum[r]=0; } inline void dfs(int r,int x) { for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]<deep[r]) { sum[e[i].v]-=x; dfs(e[i].v,x); } } inline void cut(int r) { for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) { if(!flag) return; if(sum[e[i].v]==S) { ans[++tot]=e[i].v; flag=0; dfs(e[i].v,sum[e[i].v]); sum[e[i].v]=0; deep[e[i].v]=-1; return; } cut(e[i].v); } } int main() { n=read(); int x,y; for(re int i=1;i<=n;i++) { x=read(); y=read(); if(x) add(x,i),add(i,x); else root=i; w[i]=y; S+=y; } if(S%3!=0) { puts("-1"); return 0; } S/=3; deep[root]=1; build(root); if(tot>2) cout<<min(ans[1],ans[2])<<" "<<max(ans[1],ans[2]); else puts("-1"); } ``` ### 最大子树和 [题目](https://www.luogu.org/problemnew/show/P1122) 既然已经有了这种套路，那么这道题其实就很好做了 我们读题后可以发现，这题大概就是让你减掉一些节点使剩下的树权值最大 那么我们显然是可以知道的：如果一棵子树的权值为负，那么剪掉他一定比留下他有用，所以当我们处理子树和时一旦发现有一棵子树的子树和为负，那么就将他改成0 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 16001 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int n,m,f[maxn]; int ans; int num,w[maxn],deep[maxn],head[maxn],sum[maxn]; inline int read() { char c=getchar(); int x=0,r=1; while(c<'0'||c>'9') { if(c=='-') r=-1; c=getchar(); } while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*r; } inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline void build(int r) { sum[r]+=w[r]; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; build(e[i].v); sum[r]+=sum[e[i].v]; } if(sum[r]<0) sum[r]=0; } inline int cut(int r) { for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) { int x=cut(e[i].v); if(x>0) f[r]+=x; } return f[r]; } int main() { n=read(); for(re int i=1;i<=n;i++) w[i]=read(); int x,y; for(re int i=1;i<=n-1;i++) { x=read(); y=read(); add(x,y); add(y,x); } deep[1]=1; build(1); //cut(1); for(int i=1;i<=n;i++) ans=max(sum[i],ans); printf("%d",ans); return 0; } ``` 之后再来道水题 ### 树的分解 [https://www.luogu.org/problemnew/show/P3915](题目) 这跟上面那道CF的题没有任何区别，遇到子树中节点数量为k的就切一刀 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 100001 using namespace std; struct node { int nxt,v; }e[maxn<<1]; int num,n,k,tot,T; int deep[maxn],sum[maxn],head[maxn]; void dfs(int r) { sum[r]=1; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; dfs(e[i].v); sum[r]+=sum[e[i].v]; } if(sum[r]==k) sum[r]=0,tot++; } inline void add_edge(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } int main() { T=read(); while(T--) { n=read(); k=read(); num=0; memset(head,0,sizeof(head)); int x,y; for(re int i=1;i<n;i++) { x=read(); y=read(); add_edge(x,y); add_edge(y,x); } if(n%k!=0) puts("NO"); else { memset(deep,0,sizeof(deep)); memset(sum,0,sizeof(sum)); tot=0; deep[1]=1; dfs(1); if(tot==n/k) puts("YES"); else puts("NO"); } } } ``` ## 2.树上背包 ### 选课 [题目](https://www.luogu.org/problemnew/show/P2014) 神到飞起的题目: 很经典的题目啊，大概就是树上背包的入门题 题目大意是给定一些课程，每个课程有一个学分，课程之间有依赖关系，即一些课必须在某些课被学完之后才能学，问如何在只学给定数目课程下使获得的学分最大 很神很神，一眼不会的题目 经旁边即将ak省选二轮的慎老师的提醒，发现这还有可能是个森林 就是一棵树我也不会做你还给我来个森林 那么只好愉快的去看题解 发现这跟背包很像 $f[i][j]$表示在i这棵子树里学j门课程的最大学分，对于森林这种奇异的结构我们必须把每一棵树的根于一个虚根0相连，那么在最后输出答案时直接输出$f[0][k+1]$就好了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 302 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int n,m,num,sz[maxn]; int deep[maxn],head[maxn],s[maxn],f[maxn][maxn]; inline int read() { char c=getchar(); int x=0,r=1; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline int build(int r) { if(head[r]==-1) return 0; int sum=0; for(re int i=head[r];i!=-1;i=e[i].nxt) { deep[e[i].v]=deep[r]+1; int t=build(e[i].v); sum+=t+1; for(re int j=sum;j>=0;j--) for(re int k=0;k<=t;k++) if(j-k-1>=0) f[r][j]=max(f[r][j],f[r][j-k-1]+f[e[i].v][k]); } return sum; } int main() { n=read(); m=read(); for(re int i=0;i<=n;i++) head[i]=-1; int x,y; for(re int i=1;i<=n;i++) { x=read(); s[i]=read(),f[i][0]=s[i]; add(x,i); } build(0); printf("%d",f[0][m]); return 0; } ``` ### 有线电视网 [题目](https://www.luogu.org/problemnew/show/P1273) 神题，就连即将再ak省选二轮再去ak noi的慎老师也不是一遍a的 题意冗长就不描述了 在慎老师的教育下发现了做题的人生经验 $f[i][j]$表示在以$i$为根的这棵子树里满足$j$个叶子节点的最大盈利那其实就跟课差不多 这里的sum是叶子节点的数量 注意当前状态不能是由非法状态转移过来的 ```cpp #include<iostream> #include<cstdio> #include<cstring> #define re register #define maxn 3001 using namespace std; struct node { int v,nxt,w; }e[maxn<<1]; int n,m,num; int f[maxn][maxn],s[maxn],head[maxn],deep[maxn]; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(int x,int y,int z) { e[++num].v=y; e[num].nxt=head[x]; e[num].w=z; head[x]=num; } inline int build(int r) { int sum=0; if(!head[r]) return 1; for(re int i=head[r];i;i=e[i].nxt) { deep[e[i].v]=deep[r]+1; int t=build(e[i].v); sum+=t; for(re int j=sum;j;--j) for(re int k=0;k<j;++k) { if(k&&f[e[i].v][j-k]!=-214748364&&f[r][k]!=-214748364) f[r][j]=max(f[r][j],f[r][k]+f[e[i].v][j-k]-e[i].w); if(!k&&f[e[i].v][j]!=-214748364) f[r][j]=max(f[r][j],f[e[i].v][j]-e[i].w); } } return sum; } int main() { n=read(); m=read(); int x,y; for(re int i=1;i<=n;i++) for(re int j=1;j<=m;j++) f[i][j]=-214748364; for(re int i=1;i<=n-m;i++) { int t=read(); for(re int j=1;j<=t;j++) { x=read(); y=read(); add(i,x,y); } } for(re int i=n-m+1;i<=n;i++) s[i]=read(),f[i][1]=s[i]; deep[1]=1; build(1); for(re int i=m;i>=0;i--) if(f[1][i]>=0) { printf("%d",i); return 0; } } ``` ## 3.瞎搞类 ## 会议 [题目](https://www.luogu.org/problemnew/show/P1395) 大概是我唯一自己想出来的套路了 $d$数组的含义： 在第一遍建树的过程中，$d[i]$表示在以$i$为根的这棵子树里其他节点到i的距离和为多少 由于我们钦定1为根，那么$f[1]$就就是在整棵树意义下的其他所有点到1的距离和了，有了这个有什么用呢，我们在第二遍dfs中是有用的 在第二遍dfs中，我们要用父亲的值去更新儿子，使儿子从以其为根的子树意义下的距离和变成整棵树意义下的距离和 那么式子就很好搞了，瞎搞就好了对这样例看看大概就出来了 这种父与子相互更新的题目，大概就是我唯一能自己想出来的套路了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 50001 using namespace std; struct node { int v,w,nxt; }e[maxn<<1]; int f[maxn],p[maxn],head[maxn],deep[maxn],sum[maxn],d[maxn]; int n,num; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(int x,int y) { e[++num].v=y; e[num].w=1; e[num].nxt=head[x]; head[x]=num; } inline void build(int r) { bool flag=false; sum[r]=1; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { flag=true; deep[e[i].v]=deep[r]+1; build(e[i].v); sum[r]+=sum[e[i].v]; d[r]+=sum[e[i].v]+d[e[i].v]; } if(!flag) { sum[r]=1; d[r]=0; return; } } inline void dfs(int r) { for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) { f[e[i].v]=f[r]-d[e[i].v]-sum[e[i].v]+n-sum[e[i].v]+d[e[i].v]; dfs(e[i].v); } } int main() { n=read(); int x,y; for(re int i=1;i<n;i++) { x=read(); y=read(); add(x,y); add(y,x); } deep[1]=1; build(1); f[1]=d[1]; dfs(1); int ans=999999999,mid=0; for(re int i=1;i<=n;i++) if(f[i]<ans) ans=f[i],mid=i; cout<<mid<<" "<<ans<<endl; return 0; } ``` ### [USACO10MAR]伟大的奶牛聚集 [题目](https://www.luogu.org/problemnew/show/P2986) 经典的树的中心点问题 跟上面的题一个套路，就是有了边权和点权，无非就是式子难搞一些 ```cpp #include<iostream> #include<cstdio> #include<cstring> #define re register #define maxn 100001 #define ll long long using namespace std; struct node { int v,nxt,w; }e[maxn<<1]; ll n,m,ans,num,tot; ll head[maxn],sum[maxn],s[maxn],deep[maxn],f[maxn],d[maxn]; inline ll read() { char c=getchar(); ll x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(ll x,ll y,ll z) { e[++num].v=y; e[num].nxt=head[x]; e[num].w=z; head[x]=num; } inline void build(int r) { sum[r]=s[r]; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; build(e[i].v); sum[r]+=sum[e[i].v]; d[r]+=sum[e[i].v]*e[i].w+d[e[i].v]; } } inline void dfs(int r) { for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) { f[e[i].v]=f[r]-d[e[i].v]-e[i].w*sum[e[i].v]+e[i].w*(tot-sum[e[i].v])+d[e[i].v]; dfs(e[i].v); } } int main() { n=read(); for(re int i=1;i<=n;i++) s[i]=read(),tot+=s[i]; ll x,y,z; for(re int i=1;i<n;i++) { x=read(); y=read(); z=read(); add(x,y,z); add(y,x,z); } deep[1]=1; build(1); f[1]=d[1]; dfs(1); ans=99999999999999; for(re int i=1;i<=n;i++) if(f[i]<ans) ans=f[i]; printf("%lld",ans); return 0; } ``` ### [USACO12FEB]附近的牛Nearby Cows [题目](https://www.luogu.org/problemnew/show/P3047) 写过题解了，就只丢一个链接吧 [题解](https://www.luogu.org/blog/user35178/solution-p3047) ### [ZJOI2007]时态同步 [题目](https://www.luogu.org/problemnew/show/P1131) 大概是我第一道来自zjoi的题目 我们以$f[i]$表示以$i$为根的子树里达到时态同步的最小花费， 而$d[i]$则表示在对应最小花费下的时间 所以$d[i]=max(d[i],d[j]+time[i][j])$ $j$是$i$的儿子$time[i][j]$表示$i$,$j$两点之间的边权 而$f[i]$则是$f[j]+d[i]-d[j]-time[i][j]$的和 一边dfs就可以出答案了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 1000001 #define int unsigned long long using namespace std; struct node { int v,w,nxt; }e[maxn<<1]; int head[maxn],f[maxn],deep[maxn],root; int d[maxn]; int n,m,num; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(int x,int y,int z) { e[++num].v=y; e[num].nxt=head[x]; e[num].w=z; head[x]=num; } void build(int r) { for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; build(e[i].v); d[r]=max(d[r],d[e[i].v]+e[i].w); } for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) f[r]+=(d[r]-e[i].w-d[e[i].v])+f[e[i].v]; } signed main() { n=read(); root=read(); int x,y,z; for(re int i=1;i<n;i++) { x=read(); y=read(); z=read(); add(x,y,z); add(y,x,z); } deep[root]=1; build(root); cout<<f[root]; return 0; } ``` ### 没有上司的舞会 [题目](https://www.luogu.org/problemnew/show/P1352) 经典题 $F[i][0]$表示在以$i$为根的这棵子树里不选择根节点的最大欢乐值 $F[i][1]$表示在以$i$为根的这棵子树里选择根节点的最大欢乐值 那就很好转移了 $F[i][0]+=max(f[j][1],f[j][0]);$ $F[i][1]+=f[j][0]$ $F[i][1]+=a[i]$ $A[i]$表示$i$的欢乐值，$j$为$i$的儿子 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 6001 using namespace std; struct node { int v,nxt; }e[maxn*2]; int n,num,root; int head[maxn],deep[maxn],c[maxn]; int w[maxn],f[maxn][2]; inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline int read() { char c=getchar(); int x=0,r=1; while(c<'0'||c>'9') { if(c=='-') r=-1; c=getchar(); } while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*r; } inline void build(int r) { if(!head[r]) { f[r][0]=0,f[r][1]=w[r]; return; } f[r][1]+=w[r]; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; build(e[i].v); f[r][1]+=f[e[i].v][0]; f[r][0]+=max(f[e[i].v][1],f[e[i].v][0]); } } int main() { n=read(); for(re int i=1;i<=n;i++) w[i]=read(); int x,y; for(re int i=1;i<=n-1;i++) { x=read(); y=read(); add(y,x); c[x]++; } x=read(); y=read(); for(re int i=1;i<=n;i++) if(!c[i]) { root=i; break; } deep[root]=1; build(root); printf("%d",max(f[root][0],f[root][1])); return 0; } ``` ### 战略游戏 [题目](https://www.luogu.org/problemnew/show/P2016) 其实跟没有上司的舞会蛮像的 $F[i][0]$表示以$i$为根的子树里$i$不放士兵的最少放置 $F[i][1]$表示以$i$为根的子树里$i$放士兵的最少放置 那么就有 $F[i][1]+==min(f[j][0],f[j][1])$ $F[i][1]+=1;$ $F[i][0]+=f[j][1]$ 其中$j$是$i$的儿子 ```cpp #include<cstdio> #include<cstring> #include<iostream> #define re register #define maxn 1501 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int n,m,num; int f[maxn][2],head[maxn],deep[maxn]; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline void build(int r) { f[r][1]=1; bool flag=0; for(re int i=head[r];i!=-1;i=e[i].nxt) if(!deep[e[i].v]) { flag=1; deep[e[i].v]=deep[r]+1; build(e[i].v); f[r][0]+=min(f[e[i].v][0]+1,f[e[i].v][1]); f[r][1]+=min(f[e[i].v][0],f[e[i].v][1]); } if(!flag) { f[r][0]=0; f[r][1]=1; return; } } int main() { n=read(); int p,x,y; for(re int i=0;i<=n;i++) head[i]=-1; for(re int i=1;i<=n;i++) { p=read(); y=read(); for(re int j=1;j<=y;j++) { x=read(); add(x,p); add(p,x); } } deep[1]=1; build(1); printf("%d",min(f[1][0],f[1][1])); return 0; } ``` ### [ZJOI2006]三色二叉树 [题目](https://www.luogu.org/problemnew/show/P2585) 好像还是跟没有上司的舞会蛮像的 首先这个读入比较鬼畜，大概是要递归了 于是我们再来看这题讲了些什么 经过一番读题后会发现什么红色和蓝色都是纸老虎，需要考虑的只有绿色 于是对于一个节点来说状态只有两种：绿色或不是绿色 于是我们就要分情况讨论一下了 首先是没有孩子的节点，就是叶子节点，怎么处理大概是个人都知道吧 再者是只有一个孩子，于是情况跟没有上司的舞会差不多 之后两个孩子的就需要细致考虑一下了 首先如果这个节点没有被染为绿色，那么它的两个孩子中必定有一个是绿的，而另一个则一定不是蓝的 于是就有两种情况：左儿子染成绿，右儿子不染绿 或者是左儿子不染绿，右儿子染成绿 于是对两种情况的和相应取最大值或最小值就好了 之后是这个节点染成绿色，那么两个儿子就必定都不是绿色 于是就很简单了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> #include<map> #include<set> #define re register #define maxn 500001<<1 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int head[maxn],dmax[maxn][2],dmin[maxn][2],deep[maxn]; int num,n; inline void add(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } void read_tree(int r) { char c=getchar(); if(c=='0') return; if(c=='1') { add(r,++n); add(n,r); read_tree(n); } if(c=='2') { add(r,++n); add(n,r); read_tree(n); add(r,++n); add(n,r); read_tree(n); } } void build(int r) { int sum=0,r1,r2; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; sum++; if(sum==1) r1=e[i].v; else r2=e[i].v; build(e[i].v); } if(!sum) { dmax[r][1]=1; dmax[r][0]=0; dmin[r][0]=0; dmin[r][1]=1; } if(sum==1) { dmax[r][0]=max(dmax[r1][1],dmax[r1][0]); dmax[r][1]=dmax[r1][0]+1; dmin[r][0]=min(dmin[r1][0],dmin[r1][1]); dmin[r][1]=dmin[r1][0]+1; } if(sum==2) { dmax[r][0]=max(dmax[r1][0]+dmax[r2][1],dmax[r2][0]+dmax[r1][1]); dmax[r][1]=dmax[r1][0]+dmax[r2][0]+1; dmin[r][0]=min(dmin[r1][0]+dmin[r2][1],dmin[r2][0]+dmin[r1][1]); dmin[r][1]=dmin[r1][0]+dmin[r2][0]+1; } } int main() { deep[++n]=1; read_tree(1); build(1); cout<<max(dmax[1][0],dmax[1][1])<<" "<<min(dmin[1][0],dmin[1][1]); return 0; } ``` ### [SDOI2006]保安站岗 [题目](https://www.luogu.org/problemnew/show/P2458) 用最常规的方法做并不行了，因为这里的节点是可以被父亲控制的 于是我们的数组里多开一维 $f[x][0]$表示$x$这个节点放置一个保安，且以$x$为根的子树被全部控制的最小花费，$f[x][1]$表示$x$这个节点不放保安，但以$x$为根的子树被全部控制的最小花费（就是$x$被一个放置了保安的儿子控制了），$f[x][2]$表示表示$x$这个节点不放保安，以$x$为根的子树除了$x$被全部控制的最小花费（$x$等着被父亲控制） 现在考虑一下转移就好了，$v$是$x$的儿子 $f[x][0]=\sum{min(f[v][1],f[v][2],f[v][0])}+val[x]$，显然如果$x$放了保安儿子们随便选了 $f[x][2]=\sum{min(f[v][1],f[v][0])}$显然如果$x$不放保安，儿子们只要被控制住就可以随便选了 $f[x][1]$比较特殊，和$f[x][2]$差不多，但是必须有一个$f[v][0]$被选 代码很简单了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 100005 #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define INF 999999999 int f[maxn][3]; int head[maxn],deep[maxn]; struct node { int v,nxt; }e[maxn<<1]; int n,m,num; inline int read() { char c=getchar(); int x=0,r=1; while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();} while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x*r; } inline void add_edge(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } void dfs(int r) { int flag=0; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { flag=1; deep[e[i].v]=deep[r]+1; dfs(e[i].v); f[r][0]+=min(min(f[e[i].v][0],f[e[i].v][1]),f[e[i].v][2]); f[r][2]+=min(f[e[i].v][0],f[e[i].v][1]); } f[r][1]=INF; for(re int i=head[r];i;i=e[i].nxt) if(deep[e[i].v]>deep[r]) f[r][1]=min(f[r][1],f[r][2]-min(f[e[i].v][0],f[e[i].v][1])+f[e[i].v][0]); } int main() { n=read(); int x,y,tnow,z; for(re int i=1;i<=n;i++) { x=read(); y=read(); f[x][0]=y; tnow=read(); for(re int j=1;j<=tnow;j++) z=read(),add_edge(x,z),add_edge(z,x); } deep[1]=1; dfs(1); printf("%d\n",min(f[1][0],f[1][1])); return 0; } ``` ### [USACO10NOV]拜访奶牛Visiting Cows [题目](https://www.luogu.org/problemnew/show/P2996) 依旧是没有上司的舞会的变形版 我们用$f[i][0]$表示在$i$这棵子树中不拜访$i$的最大拜访数 那$f[i][1]$表示什么就不用说了 于是就很水了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 50001 using namespace std; struct node { int v,nxt; }e[maxn<<1]; int head[maxn],f[maxn][2],deep[maxn]; int n,m,num; inline void add_edge(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } void dfs(int r) { f[r][1]=1; for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; dfs(e[i].v); f[r][0]+=max(f[e[i].v][0],f[e[i].v][1]); f[r][1]+=f[e[i].v][0]; } } int main() { n=read(); int x,y; for(re int i=1;i<n;i++) { x=read(); y=read(); add_edge(x,y); add_edge(y,x); } deep[1]=1; dfs(1); cout<<max(f[1][0],f[1][1])<<endl; return 0; } ``` ### 染色计数 [题目](https://www.luogu.org/problemnew/show/P3914) 大概算是树上计数类问题 好像很卡空间的样子 我们用$f[i][j]$表示在$i$这棵子树中根节点染成$j$颜色时的方案数 于是根据乘法原理 $f[i][j]=\prod \text{ }\sum_{p=1}^{c(j)}f[k][p]$ 其中$k$是$i$的儿子，$j!=p$，$c(k)$表示$k$这个节点能染得颜色有几种 如果按照这个方程去做的话我们的时间复杂度就是$O(n^3)$了，显然是过不了的 但是我们看看后面那个$\sum_{p=1}^{c(k)}f[k][p]$其实不就是当$j!=p$的方案总数吗 于是我们把方案总数算出来在单独减去那些颜色相同的方案数，就可以优化到$O(n^2)$了 同时由于要取模的关系，可能剪出来是负数，于是这个时候要加上模数在% 同时这道题还卡空间，非常之恶心 代码 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<vector> #define re register #define maxn 5001 #define int unsigned int using namespace std; const int mod=1e9+7; struct node { int v,nxt; }e[maxn<<1]; int head[maxn]; int f[maxn][maxn],deep[maxn],sum[maxn]; int n,m,num; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } inline void add_edge(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } void dfs(int r) { for(re int i=head[r];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[r]+1; dfs(e[i].v); for(re int j=1;j<=m;j++) f[r][j]=((long long)f[r][j]*(long long)((sum[e[i].v]-f[e[i].v][j]+mod)%mod))%mod; } for(re int i=1;i<=m;i++) sum[r]=(sum[r]+f[r][i])%mod; } signed main() { n=read(); int t; m=read(); for(re int i=1;i<=n;i++) { t=read(); for(re int j=1;j<=t;j++) f[i][read()]=1; } int x,y; for(re int i=1;i<n;i++) { x=read(); y=read(); add_edge(x,y); add_edge(y,x); } deep[1]=1; dfs(1); cout<<sum[1]<<endl; return 0; } ```
正在渲染内容...
点赞
1
收藏
0
