复兴提高DAY05树形动态规划
2025-07-07 22:19:12
发布于:上海
T1【树形动态规划】D级上司
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, d, ans[maxn], tmp[maxn]; // ans 每个员工 D 级上司, tmp记录深度所在的子树根结点
vector<int> son[maxn]; // 存储每个员工的直接下级
// cur_node 当前结点,cur_lv 当前深度
void dfs(int cur_node, int cur_lv)
{
tmp[cur_lv] = cur_node;
if (cur_lv - d > 0) // 若当前深度 - D 大于零,说明该结点有 D 级上司
ans[cur_node] = tmp[cur_lv - d];
else
ans[cur_node] = -1;// 否则没有 D 级上司
// 该结点的所有子结点都需要递归遍历
for(int j=0;j<son[cur_node].size();j++)
dfs(son[cur_node][j],cur_lv+1); //cur_node的儿子 深度加1
}
int main()
{
cin >> n >> d; //n个节点 d级上司
for (int i = 2, x; i <= n; i++)
{
cin >> x; // 该员工的直接上司
son[x].push_back(i); // i的直接上司为x(x为父节点,i为子节点)
}
dfs(1, 1);
for (int i = 1; i <= n; i++)
cout << ans[i] << endl;
return 0;
}
T2【树形动态规划】生命之树
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int a[N],dp[N]; //dp[i]:以i为根的子树中最大的权值之和
vector<int>adj[N];
int n;
void dfs(int u,int fa) //当前节点为u,其父节点为fa
{
dp[u]=a[u];
for(int j=0;j<adj[u].size();j++) //节点u所有的出边
{
int v=adj[u][j];
if(v!=fa)
{
dfs(v,u);
if(dp[v]>0)
dp[u]+=dp[v];
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]; //每个结点的权值
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
adj[x].push_back(y); //无向边邻接表存图
adj[y].push_back(x);
}
dfs(1,0);
int mx=0;
for(int i=1;i<=n;i++)
mx=max(mx,dp[i]);
cout<<mx;
return 0;
}
T3【树形动态规划】没有上司的舞会
#include<bits/stdc++.h>
using namespace std;
const int N=6e3+10;
vector<int>ve[N];
int f[N][2];
int h[N];
bool vis[N];
int n;
void dfs(int x)
{
f[x][0] = 0;
f[x][1] = h[x];
for(int j = 0; j < ve[x].size(); j++)
{
int y = ve[x][j];
dfs(y);
f[x][0] += max(f[y][0] , f[y][1]);
f[x][1] += f[y][0];
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> h[i]; //快乐指数
for(int i = 1; i <= n - 1; i++) //n-1条关系
{
int l,k;
cin >> l >> k; //k为父节点 l为子节点
ve[k].push_back(l);
vis[l] = 1;
}
int root; //根结点
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
root = i;
break;
}
}
dfs(root);
cout<<max(f[root][0],f[root][1]);
return 0;
}
T4【树形动态规划】Ksyusha and Chinchilla
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
vector<int>ve[maxn];
int siz[maxn];
int n,flag,ans;
void dfs(int x,int fa)
{
if(flag)
return;
siz[x]=1;
for(int i=0; i<ve[x].size(); i++)
{
int y=ve[x][i];
if(y==fa)
continue;
dfs(y,x);
siz[x]+=siz[y];
}
if(siz[x]>3)
flag=true;
else if(siz[x]==3)
{
if(fa)
{
siz[x]=0;
ans++;
}
}
}
int main()
{
cin>>n;
for(int i=1; i<n; i++)
{
int u,v;
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
flag=false; //false:能删除完 true:不能删除完
if(n%3)
cout<<"-1";
else
{
dfs(1,0);
if(flag)
cout<<"-1";
else
cout<<ans;
}
return 0;
}
这里空空如也
有帮助,赞一个