学做粤菜的网站,承德招聘信息网,网站dns多久刷新,课程资源网站开发 jsp定义#xff1a;树形DP也叫树状DP#xff0c;即在树上进行的DP#xff0c;是DP中较为复杂一类
1#xff1a;主体
即like拓扑排序#xff0c;从叶子节点向上更新其父节点#xff0c;从而进行dp#xff0c;确保先更新的子节点去更新其父节点#xff0c;一般使用dfs形式…定义树形DP也叫树状DP即在树上进行的DP是DP中较为复杂一类
1主体
即like拓扑排序从叶子节点向上更新其父节点从而进行dp确保先更新的子节点去更新其父节点一般使用dfs形式
void dfs(ll u,ll fa)
{dp[u]1;for(auto c:G[u]){if(c!fa){dfs(c,u);dp[u]dp[c];}}
}
【例1.2】洛谷P1352 没有上司的舞会
//P1352 没有上司的舞会
//2024.3.27 1238#includebits/stdc.h
using namespace std;
using ll long long;
const ll N 500005;
#define mod 1000000007
#define inf 1e18
#define YES coutYES\n;
#define NO coutNO\n;
#define lc p1
//左子节点
#define rc p1|1vectorlla[N],sz(N),f(N),g(N),rot(N);
void dfs(ll u,ll fa)
{//sz[u]1;for(auto c:a[u]){if(c!fa){dfs(c,u);f[u]g[c];//选择了u就不能选择他儿子g[u]max(g[c],f[c]);//不选择u也可以不选择儿子也可以选择}}
}
void solve()
{ll n;cinn;for(ll i1;in;i) cinsz[i],f[i]sz[i];//初始化每个人的兴趣度for(ll i1;in;i){ll x,y;cinxy;a[x].push_back(y);a[y].push_back(x);rot[y];}ll d0;for(ll i1;in;i){if(!rot[i]){di;//找bossbreak;}}dfs(d,0);coutmax(g[d],f[d])\n;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//ll t;cint;//while(t--) solve();return 0;
}2树形背包
3换根DP
