【算法日记】Day 17 动态规划专题——树状DP拓展（DFN序）

Abstract#树形DP#DFS#异或#DFN序1. 题目题目LeetCode 2322. 从树中删除边的最小分数核心思路以0为根DFS预处理每个节点的DFS序dfn、子树大小size、子树异或值orx。随后枚举所有边对每条边对应一个子树取两端点中深度较大的那个节点作为子树的根。对于两条边对应的子树pre和pos其中pre的DFS序较小根据它们是否包含关系计算三个连通块的异或值如果pos在pre的子树内则三个块为orx[pos]、orx[pre] ^ orx[pos]即pre子树中除去pos子树的部分、orx[1] ^ orx[pre]整棵树减去pre子树。否则三个块为orx[pre]、orx[pos]、orx[1] ^ orx[pre] ^ orx[pos]。最后计算三个值的极差更新全局最小值。复杂度时间复杂度O ( n 2 ) O(n²)O(n2)空间复杂度O ( n ) O(n)O(n)。2. 代码constintMAXN10005;classSolution{public:structEdge{intto,next;}graph[MAXN*2];intcnt,head[MAXN]{0};voidadd_edge(intu,intv){graph[cnt]{v,head[u]};head[u]cnt;}intdfnCnt;intdfn[MAXN],orx[MAXN],size[MAXN];voidf(vectorintnums,introot,intp){intidfnCnt;dfn[root]i;size[i]1;orx[i]nums[root];for(inteihead[root];ei!0;eigraph[ei].next){intvgraph[ei].to;if(vp)continue;f(nums,v,root);orx[i]^orx[dfn[v]];size[i]size[dfn[v]];}}intminimumScore(vectorintnums,vectorvectorintedges){cnt0;for(inti0;iedges.size();i){add_edge(edges[i][0],edges[i][1]);add_edge(edges[i][1],edges[i][0]);}dfnCnt0;f(nums,0,-1);intans0x3f3f3f3f;for(intei0,x,y,pre,pos,sum1,sum2,sum3;eiedges.size()-1;ei){xmax(dfn[edges[ei][0]],dfn[edges[ei][1]]);for(intejei1;ejedges.size();ej){ymax(dfn[edges[ej][0]],dfn[edges[ej][1]]);if(xy){prex;posy;}else{prey;posx;}sum1orx[pos];if(pospresize[pre]){sum2orx[pre]^orx[pos];sum3orx[1]^orx[pre];}else{sum2orx[pre];sum3orx[1]^sum2^sum1;}intminOrxmin(sum1,min(sum2,sum3));intmaxOrxmax(sum1,max(sum2,sum3));ansmin(ans,maxOrx-minOrx);}}returnans;}};3. 心得DFS序与子树区间通过DFS序将子树映射为连续区间便于判断节点间的祖先关系包含关系。dfn[u] 和 size[dfn[u]] 确定了子树的区间范围。异或的性质利用若a ^ b c则c ^ a b可以通过整棵树异或值与子树异或值快速计算出其他部分的异或值。枚举策略枚举所有边对O(n²)每条边对应一个子树取两端点中DFS序较大的节点通过判断两个子树的包含关系分情况计算三个连通块的异或值。4. 相关题目LeetCode 2458. 移除子树后的二叉树高度