Virtual NOIP II Day 8 总结

### T1 关联点 一道树上的题目，感觉难度比本卷$\text{T}2$大。 $60$分：对每个点，在以它为根的子树内进行$\text{dfs}$即可。$\text{O}(n^2)$。 $100$分：有两种做法。 1. 由于数据范围是$2\times 10^5$，因此可以考虑使用$\text{O}(n\log n)$的算法。考虑在$b$处进行统计，即找到$b$的$v_b$层祖先进行标记。为了找到$v_b$层祖先，我们可以存储每个点的$2^k$层祖先，进行倍增（二进制拆分）跳跃。 由于要记录这个点是左关联点还是右关联点，我们想到了更好的方法：在$a$的左儿子和右儿子处进行统计，即在$v_b-1$层祖先处统计。 2. 我们考虑加速找到$b$的$v_b$层祖先的过程。我们可以$\text{dfs}$遍历整棵树，并用一个栈储存当前在函数调用栈帧中的节点（类似$\text{Tarjan}$的`stack`）。遍历到点$x$时，栈中的节点都是$x$的祖先，我们只需计算出$v_b$层祖先的深度即可直接访问。时间复杂度$\text{O}(n)$。 其实$\text{O}(n)$的代码比$\text{O}(n\log n)$的代码还要短，但是可能我学数据结构学傻了吧…… 下面附上$\text{O}(n)$的代码： ```cpp #include <cstdio> #define MAXN 200005 using namespace std; typedef int io_t; io_t uread(void); void uwrite(io_t x,char spliter=' '); int n; int lch[MAXN],rch[MAXN]; int con[MAXN]; //Mark at the lc/rc int depth[MAXN]; int v[MAXN]; int st[MAXN]; int stop; void dfs(int x); int main(void){ n=uread(); for (int i=1;i<=n;i++) v[i]=uread(); for (int i=1;i<=n;i++){ int lc,rc; lc=uread(),rc=uread(); lch[i]=lc,rch[i]=rc; } stop=0; depth[1]=0; dfs(1); for (int i=1;i<=n;i++){ uwrite(con[lch[i]]); uwrite(con[rch[i]]); putchar('\n'); } return 0; } void dfs(int x){ st[stop++]=x; if (depth[x]>=v[x]) con[st[depth[x]-v[x]+1]]++; if (lch[x]){ depth[lch[x]]=depth[x]+1; dfs(lch[x]); } if (rch[x]){ depth[rch[x]]=depth[x]+1; dfs(rch[x]); } stop--; } ``` ### T2 小奇的日程表 一道$\text{T}1$水平的题目，不知道为什么放在这里？ 直接暴力模拟即可。注意标记数组不要爆空间，因此不能用`int`，只能用`bool`或`bitset`。 ### T3 送分题 把分送掉的题目。一道比较好的树形$\text{dp}$，和[黑点](https://vjudge.net/problem/CodeChef-BLACKCOM)有一点类似（当然难度不一定是一个级别的），可以用来领悟树形$\text{dp}$的基本套路。 毕克老师说，树形$\text{dp}$题目的数据范围可以用来辅助状态设计。于是我们观察数据范围：$n\le 10000,k\le 100$。于是我们就可以考虑设计$\text{O}(nk)$的状态。 我们设$f[i][j]$为：以$i$为根的子树中，所选节点到$i$距离$\ge j$，且合法的选择方案中点权和的最大值。那么，我们要考虑$f[i][j]$的转移。 树形$\text{dp}$的转移有一个套路：遍历子节点前，预处理父节点信息；在遍历子节点的同时，先将子节点的信息和父节点的信息进行处理，再将子节点的信息合并到父节点的信息中；最后根据父节点的信息处理答案。 这题也遵循这样的套路。 设当前遍历到的父节点为$x$。 预处理父节点信息这一步在本题中不需要，我们直接遍历子节点。设遍历到的子节点为$v$。 接下来考虑用$f[v]$更新$f[x][j]$。在信息合并中，有以下两种情况： 1. 距离$x$等于$j$的节点在前面遍历（即信息已被合并）的子节点中，那么$f[x][j]$可以被更新为$f[x][j]+f[v][i]$，其中$i=\max (j-1,k-j)$。（对$i$的要求可以理解为，既要求$i+1+j>k$，又要求$i\ge j$。注意到$x$的距离等于到$v$的距离$+1$。） 2. 距离$x$等于$j$的节点在新的（即当前遍历到）的子节点中，那么$f[x][j]$可以被更新为$f[x][i]+f[v][j-1]$，其中$i=\max(j,k+1-j)$。 尤其注意上面$j$的范围应为$[1,k+1]$。另外，我们把$f$打造为一个后缀$\max$的数组，即$j$越小，$f[x][j]$越大。这一点在“所选节点到$i$距离$\ge j$“中就可以体现。还有一点是，由于$f[v][k+1]$的信息已经被合并到$f[v][k]$中（前缀$\max$），我们在转移时无需考虑$f[v][k+1]$。 还要注意的一点是，我们在更新$f[x][j]$的值的时候，要把更新的值存到临时数组中，更新完毕后再转移回$f$数组，否则可能导致同一个权值被重复累加（这是一种类似$01$背包倒序转移的思想）。 最后，要根据父节点的信息处理答案，即我们要考虑选择父节点的情形。要选择父节点，其余选择的点到它的距离就至少是$k+1$。因此$f[x][0]=\max(f[x][1],f[x][k+1]+w[x])$。其实在这一步我们已经把$f[x][k+1]$的值使用完了，在以后的转移中它就没有用了。 在考试中，我在书写这道题的代码时，把上面的坑几乎全部跳了一遍（逃）。然而到考试结束我都没有发现的坑是，我把临时数组转移和求前缀$\max$放在了同一个循环中，由于$f[x][k+1]$不需要求前缀$\max$，因此那个循环就没有到达$k+1$，从而$f[x][k+1]$没有从临时数组中转移出来，最终造成某些状态下答案偏小，导致$\text{WA}$了$2$个点。这个坑点确实难以发现（难以对撞），对拍了很多次都没能发现。因此，对拍通过、通过大样例并不意味着这个程序是正确的，只是意味着它也许能够得到**大部分**的分数。想要保证程序的执行过程和心里想的一样，还是要进行代码审核。 下面附上关键部分的代码： ```cpp void dfs(int x,int pa){ for (int ei=fst[x];ei;ei=nxt[ei]){ int v=g[ei]; if (v==pa) continue; dfs(v,x); for (int j=1;j<=kp1;j++){ //kp1 means k+1 //f[x][j]=back_max_f[v][max(j-1,k-j)] //Decide by father int considerj=max(j-1,k-j); tempf[j]=f[x][j]+f[v][considerj]; } for (int j=1;j<=kp1;j++){ //f[v][j-1] (dis==j) //Decide by child int considerj=max(j,kp1-j); tempf[j]=max(tempf[j],f[v][j-1]+f[x][considerj]); } //f[v][k+1]:ignore. tempf[0]=0; for (int j=kp1;j>=0;j--){ //Important! j=kp1 not j=k. //Otherwise tempf[k+1] will lose tempf[j]=max(tempf[j],tempf[j+1]); f[x][j]=tempf[j]; } } f[x][0]=max(f[x][0],f[x][k+1]+w[x]); ans=max(ans,f[x][0]); } ```