注：买的去年的题，本地OI赛制，排名按当年的计算。
又双叒叕挂大分，T2离正解只差一步（但输出格式错了，10pts -> 0pts）,T3花了 1h 30min 打出了正解但由于线段树标记没开 long long 爆 55 了
把 1 个人劈成 4 半，用树状数组维护区间人数和， O(nlogn)O(n\log n)O(nlogn) 就可以过掉此题。
代码：
考场都看出来用角谷猜想逆推了，但没想到负数怎么处理，结果直接 0 分。
角谷猜想，对于任意一个正整数 n，进行如下变换：若为偶数则变为 n/2，否则变为 n*3+1
负数的话先用后两种操作降为 100 以内（此时它会出现循环），然后一直加 ddd 直到大于等于 111 为止，然后再正着一遍角谷猜想即可得出答案。
代码：
WARNING：本题思维难度不大，但代码实现难度极高，提高组及以下 OIer 请在成年人的陪同下谨慎观看！
考虑暴力拆式子：
AxA_xAx
=dis2(x,0)+∑dis2(x,y)=dis^2(x,0)+\sum dis^2(x,y)=dis2(x,0)+∑dis2(x,y)
=dis2(x,0)+∑(depx+depy−deplca(x,y)×2)2=dis^2(x,0)+\sum(dep_x+dep_y-dep_{lca(x,y)}\times 2)^2=dis2(x,0)+∑(depx+depy−deplca(x,y)×2)2
=dis2(x,0)+∑(depx2+depy2+deplca(x,y)2×4+depx×depy×2−depx×deplca(x,y)×4−depy×deplca(x,y)×4)=dis^2(x,0)+\sum({dep_x}^2+{dep_y}^2+{dep_{lca(x,y)}}^2\times 4 +dep_x\times dep_y \times 2-dep_x\times dep_{lca(x,y)} \times 4-dep_y\times dep_{lca(x,y)} \times 4)=dis2(x,0)+∑(depx2+depy2+deplca(x,y)2×4+depx×depy×2−depx×deplca(x,y)×4−depy×deplca(x,y)×4)
=dis2(x,0)+∑depx2+∑depy2+4×∑deplca(x,y)2+2×depx×∑depy−4×depx×∑deplca(x,y)−4×∑depy×deplca(x,y)=dis^2(x,0)+\sum {dep_x}^2+\sum{dep_y}^2+4\times\sum {dep_{lca(x,y)}}^2+2\times dep_x\times\sum dep_y-4\times dep_x\times\sum dep_{lca(x,y)}-4\times\sum dep_y \times dep_{lca(x,y)}=dis2(x,0)+∑depx2+∑depy2+4×∑deplca(x,y)2+2×depx×∑depy−4×depx×∑deplca(x,y)−4×∑depy×deplca(x,y)
第 1,21,21,2 项（dis2(x,0)dis^2(x,0)dis2(x,0)，∑depx2\sum {dep_x}^2∑depx2）：这个应该不难 O(1)\mathcal{O}(1)O(1) 求出。
第 3,53,53,5 项（∑depy2\sum{dep_y}^2∑depy2，2×depx×∑depy2\times dep_x\times\sum dep_y2×depx×∑depy）：可以顺便维护前缀和，同样可以 O(1)\mathcal{O}(1)O(1) 求出。
第 666 项（4×depx×∑deplca(x,y)4\times dep_x\times\sum dep_{lca(x,y)}4×depx×∑deplca(x,y)）：可以采用树剖，将 yyy 到 000 的路径每一段边都加 111，查询出的 xxx 到 000 路径上的权值和即为答案。
第 777 项（4×∑depy×deplca(x,y)4\times\sum dep_y \times dep_{lca(x,y)}4×∑depy×deplca(x,y)）：与第 666 项同理，只不过边上的权值加的是 depydep_ydepy。
第 444 项（4×∑deplca(x,y)24\times\sum {dep_{lca(x,y)}}^24×∑deplca(x,y)2）：这是最难的一项，不过仍然可以维护，考虑平方数列 1,4,9,16,...1,4,9,16,...1,4,9,16,... 它的差分数组是 1,3,5,7,...1,3,5,7,...1,3,5,7,... 因此只要维护区间加等差数列即可，由于每次都是修改到根结点的所以不存在链反向的情况。
总复杂度 O(nlogn)\mathcal{O}(n\log n)O(nlogn)。
代码：
注意线段树的 tag 一定要开 long long，因为单次的累加不会爆但累加
设 dpidp_idpi 为第 iii 个时间如果牛牛还没下班，他的最大欢乐值。
转移方程不难，但要注意牛牛不能在接完所有人之后摸鱼，且必须接完所有人。
加上点小优化可以做到 O(n2)\mathcal{O}(n^2)O(n2)（跑不满），目前尚未弄懂如何用李超线段树优化。
//后记&总结：本次考试时间分配极不合理， T1 其实就花了 10min ，本来是占很大优势的，T2离正解只差一步之遥，但却把大笔的时间押在了 T3 上，虽然最后也打出来了，却因为没开 long long 挂了 45 分，且因此没时间打 T4 的 dp。总而言之还是要调整好自己的状态，找好自己的节奏，这样才能发挥出真实的实力。