9.18 阿里国际笔试

第二题：会存树就能做，输入的时候统计一下已经两端都是红色的边的数量a，然后对每个白色节点i访问一下看与它相连的点为红色的树量b_i, ans = max(ans, a+b_1)第三题: 答案数：C(n,3)*676*26^(n-3)。需要会快速幂

给我面到流鼻血，真丢人，乞求算法题(笔试ak)也没有，想着算法救救我----直接挂，那我要变成黑子了，第一次见又要说又要在白板上写答案的，我说完面试官一点反应也没有，感觉就是你说完了好下一个问题，不是真有人问红黑树的插入和删除怎么实现的啊，

做第一题就做了半天，一开始o(n)空间复杂度爆堆，优化成O（1）空间不爆堆了，然后一直超时。。用JAVA就能过33.3，换成C++过47.3，一直在改这个题，后面都不怎么有时间写了。直接算应该可以是o(1)时间复杂度，但是真的有直接O(1)算（2^(10^9) ) % (10 ^ 9 + 7)的方法吗

​题目描述：游游拿到了一棵树，其中每个节点上有一个数字（＇0＇～＇9＇）。现在游游定义f(i)为：以i号节点为起点时，取一条路径，上面所有数字拼起来是3的倍数的方案数。现在小红希望你求出f(1)到f(n)的值，你能帮帮她吗？注：前导零也是合法的。更好的观看体验请移步：https://blog.csdn.net/qq_67243927/article/details/138507852?spm=1001.2014.3001.5502题解：暴力：从每个根开始暴力，发现会超时正解：树形DP+换根注意到题目要求的是拼合为3的倍数，根据3的倍数的性质，我们只需要对每位数求和看是否为3的倍数即可,动态规划...