2020.02.03日常总结

$\color{green}{洛谷P3478\ \ \ [POI2008]STA-Station}$洛谷P3478   [POI2008]STA−Station

$\color{blue}{【题意】：}$【题意】： 给您一棵有$N$N个点的无根树，求一个点，以这个点为根的树时，所有点的深度之和最大。$1 \leq N \leq 1 \times 10^6$1≤N≤1×106。

$\color{blue}{【思路】：}$【思路】： 首先，我们求出以$1$1为根（当然，以其它点为根也可以，毕竟是无根树嘛），求出此时所有点的深度和$S_1$S1​和子树大小$Size_x$Sizex​。

考虑从一个点$u$u向下移动到它的儿子$v$v时，总答案有什么变化。很明显，$v$v的子树内的节点的深度全部$-1$−1，而其它的点的深度$+1$+1，即：

$S_v=S_u-Size_v+(N-Size_v)=S_u+N-2 \times Size_v$Sv​=Su​−Sizev​+(N−Sizev​)=Su​+N−2×Sizev​

有了它，我们就可以$O(N)$O(N)处理啦——

$\color{blue}{【代码】：}$【代码】：


$\color{blue}{【语法点透析】：}$【语法点透析】：

• add(read(),read())：这句话根本不像我们想象的那么“单纯”，它是反过来的。什么意思？即输入1 2，实际上运行的是add(2,1)，而不是add(1,2)。
• e[N<<1]：为什么要两倍空间？不是已经确定了根为$1$1吗？其实，哪怕我们知道根是什么，我们仍然不能在输入时就确定这棵树的形态，所以我们仍然不知道谁是父亲谁是儿子，所以还是得两倍空间。