树上dp学习总结2
今天也是侥幸刷了两道树上dp的问题，第一个还算简单，但是第二个真的可以说是我碰到的蓝题之首，做了一个晚上我只能留下了不争气的口水（太饿了，该吃夜宵了）
P1131 [ZJOI2007] 时态同步
思路：一开始我想的是深搜一遍，然后求出每个节点到根节点的距离，然后找到最大值，然后求出所有的叶子结点和根结点的差值即可
但是这是不对的，因为如果这样会重复计算一些公共边，导致最后的结果产生错误 ，因此我们只需要每次将处理的叶子结点能够持平就可以了
如图所示
因此我们就可以写出代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> edges[500005];
int n, rt;
long long f[500005], ans; void dfs(int v, int parent)
{int len = edges[v].size(); for (int i = 0; i < len; i++) { int u = edges[v][i].first; int weight = edges[v][i].second; if (u == parent) continue; dfs(u, v); f[v]=max(f[v], f[u] + weight); //计算最大权重 } for (int i = 0; i < len; i++) { int u = edges[v][i].first; int weight = edges[v][i].second; if (u == parent) continue; ans += (f[v]-f[u]-weight); }
}
signed main()
{ cin >> n >> rt; for (int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; edges[a].emplace_back(b, c); edges[b].emplace_back(a, c); } dfs(rt,-1); cout<<ans; return 0;
}P2279 [HNOI2003] 消防局的设立
思路：这题是我真没想到的，巨难的题目，五个状态转移方程，看了大犇的代码才会写，只能说我还是个小蒟蒻
先来说一下状态转移数组的含义：
f[i][0]表示可以覆盖到从节点i向上2层的最小消防站个数
f[i][1]表示可以覆盖到从节点i向上1层的最小消防站个数
f[i][2]表示可以覆盖到从节点i向上0层的最小消防站个数
f[i][3]表示可以覆盖到从节点i向上-1层的最小消防站个数
f[i][4]表示可以覆盖到从节点i向上-2层的最小消防站个数什么叫做覆盖呢？就是说，确保消防站的覆盖范围可以覆盖到其层数以及其子树
比如说，f[ v ] [ 1]就是说要覆盖其父亲节点以及包括其自身的所有子树
f[ v ] [3] 就是要包含其儿子以及所有子孙的子树
因此我们可以找到状态转移方程
这里直接引用大犇说的话了，引用链接：大犇的题解文章
因此我们就可以写出dfs函数，完成这道题了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> G[1005];
int f[1005][5];
void dfs(int v)
{ f[v][0] = 1; f[v][3] = 0; f[v][4] = 0; for (int u:G[v]) { dfs(u); f[v][0]+=f[u][4]; f[v][3]+=f[u][2]; f[v][4]+=f[u][3]; } if (G[v].empty()) { f[v][1]=f[v][2]=1; } else { f[v][1]=f[v][2]=0x3f3f3f3f; for(int i = 0;i<G[v].size();i++) { int u=G[v][i]; int f1=f[u][0]; int f2=f[u][1]; for (int j=0;j<G[v].size();j++) { if (i == j) continue; int t=G[v][j]; //除了u外的别的子树 f1+=f[t][3]; f2+=f[t][2]; } f[v][1]=min(f[v][1],f1); f[v][2]=min(f[v][2],f2); } } for(int i=1;i<=4;i++) { f[v][i]=min(f[v][i],f[v][i-1]); }
}
signed main()
{ cin>>n; memset(f,0x3f3f3f3f,sizeof(f));for (int i=2;i<=n;i++) { int v; cin>>v; G[v].push_back(i); } dfs(1); cout<<f[1][2]<<endl; return 0;
}