【算法日记】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. 代码

constintMAXN=10005;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(vector<int>&nums,introot,intp){inti=++dfnCnt;dfn[root]=i;size[i]=1;orx[i]=nums[root];for(intei=head[root];ei!=0;ei=graph[ei].next){intv=graph[ei].to;if(v==p)continue;f(nums,v,root);orx[i]^=orx[dfn[v]];size[i]+=size[dfn[v]];}}intminimumScore(vector<int>&nums,vector<vector<int>>&edges){cnt=0;for(inti=0;i<edges.size();++i){add_edge(edges[i][0],edges[i][1]);add_edge(edges[i][1],edges[i][0]);}dfnCnt=0;f(nums,0,-1);intans=0x3f3f3f3f;for(intei=0,x,y,pre,pos,sum1,sum2,sum3;ei<edges.size()-1;++ei){x=max(dfn[edges[ei][0]],dfn[edges[ei][1]]);for(intej=ei+1;ej<edges.size();++ej){y=max(dfn[edges[ej][0]],dfn[edges[ej][1]]);if(x<y){pre=x;pos=y;}else{pre=y;pos=x;}sum1=orx[pos];if(pos<pre+size[pre]){sum2=orx[pre]^orx[pos];sum3=orx[1]^orx[pre];}else{sum2=orx[pre];sum3=orx[1]^sum2^sum1;}intminOrx=min(sum1,min(sum2,sum3));intmaxOrx=max(sum1,max(sum2,sum3));ans=min(ans,maxOrx-minOrx);}}returnans;}};

3. 心得

• DFS序与子树区间：通过DFS序将子树映射为连续区间，便于判断节点间的祖先关系（包含关系）。dfn[u] 和 size[dfn[u]] 确定了子树的区间范围。

• 异或的性质：利用若a ^ b = c则c ^ a = b，可以通过整棵树异或值与子树异或值快速计算出其他部分的异或值。

• 枚举策略：枚举所有边对（O(n²)），每条边对应一个子树（取两端点中DFS序较大的节点），通过判断两个子树的包含关系，分情况计算三个连通块的异或值。

4. 相关题目

• LeetCode 2458. 移除子树后的二叉树高度