V
主页
【算法进阶】【基环树基础】基环树dp P2607[ZJOI2008]骑士 基环树+tarjan边双连通分量+树形动态规划+线性动态规划-信息学竞赛
发布人
首次接触基环树，给个完整代码：（专栏观看更佳） https://www.bilibili.com/read/cv23695707 #include<bits/stdc++.h> using namespace std;typedef long long ll;const ll N=1e6+2; double K;stack<ll> st;bool c[N];vector<ll> v[N],g; ll n,p[N],x,cnt,dfn[N],low[N],tot,dp[N][2],f[N][2][2],i,j,ans; inline void dfs(ll x,ll fa){ dfn[x]=low[x]=++cnt,st.push(x);int w=0; for(ll t:v[x]){ if(t==fa){ w++; if(w==1)continue; } if(!dfn[t])dfs(t,x); low[x]=min(low[x],low[t]); } if(dfn[x]==low[x]){ if(st.top()==x){st.pop();return;} while(st.top()!=x)c[st.top()]=1, g.push_back(st.top()),st.pop(); c[x]=1,g.push_back(x),st.pop(); } } inline void dfs2(ll x,ll fa){ dp[x][1]=p[x]; for(ll t:v[x])if(t!=fa&&!c[t])dfs2(t,x), dp[x][0]+=max(dp[t][0],dp[t][1]),dp[x][1]+=dp[t][0]; } int main(){ scanf("%lld",&n); for(i=1;i<=n;i++)scanf("%lld%lld",&p[i],&x), v[x].push_back(i),v[i].push_back(x); for(x=1;x<=n;x++)if(!dfn[x]){ while(!st.empty())st.pop(); g.clear(),g.push_back(0),dfs(x,0),tot=g.size()-1; if(tot==0)continue; for(ll t:g)if(t!=0)dfs2(t,0); f[1][1][1]=dp[g[1]][1], f[1][0][0]=f[1][0][1]=f[1][1][0]=dp[g[1]][0]; for(i=2;i<=tot;i++)for(j=0;j<=1;j++)f[i][j][0]= dp[g[i]][0]+max(f[i-1][j][0],f[i-1][j][1]), f[i][j][1]=dp[g[i]][1]+f[i-1][j][0]; ans+=max(f[tot][0][1],max(f[tot][0][0],f[tot][1][0])); } return printf("%lld\n",ans),0; }
打开封面
下载高清视频
观看高清视频
视频下载器
【算法进阶】【动态规划百练】简单状压dp与滚动数组优化 P5005 中国象棋 - 摆上马 -信息学竞赛
【算法进阶】【动态规划-8概率与期望动态规划】dp，永远的噩梦？并不是！代码最短的dp题！CF235B Let's Play Osu!-信息学竞赛
【算法进阶】【树分治进阶】点分树的基本概念及应用-信息学竞赛
【算法进阶】【有向图上的动态规划】有向图tarjan缩点与拓扑排序动态规划详解-信息学竞赛
【复赛冲刺训练】普及组满分训练（一）动态规划总结与练习-信息学竞赛
【算法进阶】【动态规划-7数位动态规划】最简单的dp-数位dp！数位dp知识点与例题Segment Sum详解-信息学竞赛
【算法进阶】【动态规划百练】思维+状态压缩动态规划CF1391D 505-信息学竞赛
【算法进阶】【虚树】虚树的建立与简单应用-信息学竞赛
【算法进阶】【树上技巧】一些比较常见的树上trick-信息学竞赛
【算法进阶】【动态规划百练】简单数位dp题目P2188 小Z的 k 紧凑数-信息学竞赛
【算法进阶】【动态规划百练】状态压缩动态规划+BFS P2622 关灯问题II-信息学竞赛
【算法进阶】【构造题选讲】简单构造技巧讲解-信息学竞赛
【算法进阶】【动态规划-5树形动态规划】树形dp例题精讲、杂题泛讲-信息学竞赛
【算法进阶】【动态规划百练】矩阵快速幂优化动态规划P2151[SDOI2009]HH去散步-信息学竞赛
【算法进阶】【反悔贪心】反悔贪心及例题CF865D Buy Low Sell High讲解-信息学竞赛
【算法进阶】【动态规划百练】会这一题，区间dp就掌握了！CF1771D Hossam and (sub-)palindromic tree - 信息学奥赛
【算法进阶】【分块算法】分块实战，loj.ac6277~6281 数列分块入门1~5 - 信息学竞赛
【算法进阶】【严格次小生成树】Kruskal最小生成树+树上倍增详解-信息学竞赛
【复赛冲刺训练】普及组满分冲刺训练（二）线性动态规划专练-信息学竞赛
【算法进阶】【简单博弈论-Nim游戏】博弈论简介及Nim游戏必胜策略推导过程-信息学竞赛
【算法进阶】【优先队列】优先队列 ST表 NOI2010真题 P2048 [NOI2010] 超级钢琴精讲-信息学竞赛
【算法进阶】【贪心-过河问题】更复杂的贪心，过河问题情况详解-信息学竞赛
【算法进阶】【带权并查集/并查集复习】最后一次学习简单并查集！学不会以后各种算法都听不懂！ - 信息学竞赛
【算法进阶】【网络流建模】dinic算法的应用，网络流建模例题-信息学竞赛
【算法进阶】【动态规划百练】状压dp货郎挑担问题CF8C Looking for Order-信息学竞赛
【算法强化】【线段树优化动态规划】必学知识点！高级数据结构与动态规划的完美结合！P2418 yyy loves OI IV-信息学竞赛
【算法进阶】【数论分块（整除分块）】数论分块与经典例题讲解-信息学竞赛
【算法进阶】【杂题选讲】Minimum spanning tree for each edge最小生成树&树上倍增练习题-信息学竞赛
【算法进阶】【数据结构百练】ST表 单调队列 线段树 CF1195E OpenStreetMap-信息学竞赛
【算法进阶】【得分技巧-根号分治2】例题[POI2015] ODW讲解-信息学竞赛
【算法进阶】【杂题选讲】简单网络流建模P2071座位安排-信息学竞赛
【算法强化】【动态规划-6动态动态规划】ddp动态动态规划，树形动态规划，树链剖分，广义矩阵乘法-信息学竞赛
【算法进阶】【数论-组合初步】排列组合二项式定理Lucas定理P1350车的放置精讲-信息学竞赛
【算法进阶】【拉格朗日插值】拉格朗日插值，解决多点确定函数问题-信息学竞赛
【算法强化】【斜率优化动态规划】动态规划的优化之斜率优化DP-信息学竞赛
【算法进阶】【树链剖分】树链剖分（重链剖分）精讲-信息学竞赛
【算法进阶】【动态规划百练-IOI1998 Polygon】上古IOI动态规划题目讲解-信息学竞赛
【算法进阶】【数据结构选讲】可持久化Trie、李超树、左偏树混讲-信息学竞赛
【算法进阶】【线段树的应用】线段树维护动态区间最大子段和P4513 小白逛公园-信息学竞赛
【算法进阶】【数据结构-珂朵莉树】随机化区间推平操作的利器-信息学竞赛
