阿里国际笔试

三道编程只有第一题会做😅😅，第二题写半天0

​题目描述：游游拿到了一棵树，其中每个节点上有一个数字（＇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的倍数即可,动态规划...

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

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