小红的子树操作
小红的子树操作
小红拿到了一棵有根树，i号节点的权值为ai。已知1号节点为根节点。
小红有g次操作，每次操作会选择一个节点x，使得x为根的子树上，所有节点的权值乘以y。
小红想知道，在q次操作结束以后，对于i∈[1,n]，以节点i为根的子树的所有点权值乘积末尾有多少个0?
输入描述
第一行输入一个正整数n，代表节点的数量
第二行输入n个正整数ai，代表每个节点的权值。
接下来的n-1行，每行输入两个正整数u和v，代表节点u和节点v有一条边相连。
接下来的一行输入一个正整数q，代表操作次数。
1≤n,q≤10^5 1 ≤ai,y≤10^9 1≤x,u,v≤n
输出描述
输出一行n个正整数，分别代表1号节点到n号节点，每个节点的子树权值乘积尾零的数量。
输入
5
1 2 6 3 1
1 2
1 3
2 4
2 5
1
2 5
输出
2 1 ０００
说明
操作后2号、4号、5号节点都乘以5，每个节点的权值分别是[1,10,6,15,5]
1号节点为根的子树乘积是4500，末尾有2个0。
2号节点为根的子树乘积是750，末尾有1个0。
3号节点为根的子树乘积是6，末尾有0个0。
4号节点为根的子树乘积是15，末尾有0个0。
5号节点为根的子树乘积是5，末尾有0个0。
题意
小红拿到了一棵有根树，i 号节点的权值为 ai 。已知1号节点为根节点。
小红有q次操作，每次操作会选择一个节点x，使得x为根的子树上，所有节点的权值乘以y。
小红想知道，在q次操作结束以后，对于节点 i，以节点 i 为根的子树的所有点权值乘积末尾有多少个0？
1 <= n, q <= 10^5
1 <= ai, y <= 10^9
作者：今夕kpole链接：https://www.nowcoder.com/discuss/475037372275523584来源：牛客网
我的解答1
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static Set<Integer> visited = new HashSet<>();
// 每个子树的所有的节点id
public static Map<Integer, Set<Integer>> subTreeNodes = new HashMap<>();
public static Set<Integer> DFS(Map<Integer, List<Integer>> edges, int nodeId) {
Set<Integer> ret = new HashSet<>();
//if(visited.contains(nodeId)) return ret;
ret.add(nodeId);
visited.add(nodeId);
// 遍历所有子节点
List<Integer> children = edges.get(nodeId);
if (children != null) {
for (int childNodeId : children) {
// 如果子节点被遍历过
if (visited.contains(childNodeId)) {
continue;
}
Set<Integer> childNodeSet = DFS(edges, childNodeId);
ret.addAll(childNodeSet);
}
}
subTreeNodes.put(nodeId, ret);
return ret;
}
public static int getFiveCount(int value) {
int ret = 0;
while (value % 5 == 0) {
ret++;
value /= 5;
}
return ret;
}
public static int getTwoCount(int value) {
int ret = 0;
while (value % 2 == 0) {
ret++;
value /= 2;
}
return ret;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ai[] = new int[n + 1];
int aitwoCount[] = new int[n + 1];
int aifiveCount[] = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
ai[i] = in.nextInt();
aifiveCount[i] = getFiveCount(ai[i]);
aitwoCount[i] = getTwoCount(ai[i]);
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
Map<Integer, List<Integer>> edges = new HashMap<>();
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt();
int b = in.nextInt();
List<Integer> child1 = edges.get(a);
if (child1 == null) {
child1 = new ArrayList<Integer>();
edges.put(a, child1);
}
child1.add(b);
List<Integer> child2 = edges.get(b);
if (child2 == null) {
child2 = new ArrayList<Integer>();
edges.put(b, child2);
}
child2.add(a);
}
// 找到所有子树的所有节点集合，建立映射关系。
DFS(edges, 1);
int q = in.nextInt();
for (int i = 0; i < q; i++) {
int x = in.nextInt();
int y = in.nextInt();
Set<Integer> allNodes = subTreeNodes.get(x);
// Integer[] temp = allNodes.toArray(new Integer[0]);
// Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
// System.out.println();
for (int nodeId : allNodes) {
aifiveCount[nodeId] += getFiveCount(y);
aitwoCount[nodeId] += getTwoCount(y);
}
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
StringBuilder resultStr = new StringBuilder();
for (int i = 1; i <= n; i++) {
Set<Integer> allNodes = subTreeNodes.get(i);
int twoCount = 0;
int fiveCount = 0;
for (int nodeId : allNodes) {
twoCount += aitwoCount[nodeId];
fiveCount += aifiveCount[nodeId];
}
resultStr.append(Math.min(twoCount, fiveCount) + " ");
}
System.out.print(resultStr.toString());
// 注意 hasNext 和 hasNextLine 的区别
// while (in.hasNextInt()) { // 注意 while 处理多个 case
// int a = in.nextInt();
// int b = in.nextInt();
// System.out.println(a + b);
// }
}
}
运行超时，通过率40%。
我的解答2
将保存每个子树的所有的节点id的Map<Integer, Set<Integer>>改为Map<Integer, List<Integer>>：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static Set<Integer> visited = new HashSet<>();
// 每个子树的所有的节点id
public static Map<Integer, List<Integer>> subTreeNodes = new HashMap<>();
public static List<Integer> DFS(Map<Integer, List<Integer>> edges, int nodeId) {
List<Integer> ret = new ArrayList<>();
//if(subTreeNodes.containsKey(nodeId)) return subTreeNodes.get(nodeId);
ret.add(nodeId);
visited.add(nodeId);
// 遍历所有子节点
List<Integer> children = edges.get(nodeId);
if (children != null) {
for (int childNodeId : children) {
// 如果子节点被遍历过
if (visited.contains(childNodeId)) {
continue;
}
List<Integer> childNodeSet = DFS(edges, childNodeId);
ret.addAll(childNodeSet);
}
}
subTreeNodes.put(nodeId, ret);
return ret;
}
public static int getFiveCount(int value) {
int ret = 0;
while (value % 5 == 0) {
ret++;
value /= 5;
}
return ret;
}
public static int getTwoCount(int value) {
int ret = 0;
while (value % 2 == 0) {
ret++;
value /= 2;
}
return ret;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ai[] = new int[n + 1];
int aitwoCount[] = new int[n + 1];
int aifiveCount[] = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
ai[i] = in.nextInt();
aifiveCount[i] = getFiveCount(ai[i]);
aitwoCount[i] = getTwoCount(ai[i]);
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
Map<Integer, List<Integer>> edges = new HashMap<>();
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt();
int b = in.nextInt();
List<Integer> child1 = edges.get(a);
if (child1 == null) {
child1 = new ArrayList<Integer>();
edges.put(a, child1);
}
child1.add(b);
List<Integer> child2 = edges.get(b);
if (child2 == null) {
child2 = new ArrayList<Integer>();
edges.put(b, child2);
}
child2.add(a);
}
// 找到所有子树的所有节点集合，建立映射关系。
DFS(edges, 1);
int q = in.nextInt();
for (int i = 0; i < q; i++) {
int x = in.nextInt();
int y = in.nextInt();
List<Integer> allNodes = subTreeNodes.get(x);
// Integer[] temp = allNodes.toArray(new Integer[0]);
// Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
// System.out.println();
for (int nodeId : allNodes) {
aifiveCount[nodeId] += getFiveCount(y);
aitwoCount[nodeId] += getTwoCount(y);
}
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
StringBuilder resultStr = new StringBuilder();
for (int i = 1; i <= n; i++) {
List<Integer> allNodes = subTreeNodes.get(i);
int twoCount = 0;
int fiveCount = 0;
for (int nodeId : allNodes) {
twoCount += aitwoCount[nodeId];
fiveCount += aifiveCount[nodeId];
}
resultStr.append(Math.min(twoCount, fiveCount) + " ");
}
System.out.print(resultStr.toString());
// 注意 hasNext 和 hasNextLine 的区别
// while (in.hasNextInt()) { // 注意 while 处理多个 case
// int a = in.nextInt();
// int b = in.nextInt();
// System.out.println(a + b);
// }
}
}
运行超时，通过率70%。可见Hashset的运行效率比ArrayList低。
我的解答3
按照作者：今夕kpole的如下链接帖子的思路实现，程序还是运行超过1s，依然无法AC。
https://www.nowcoder.com/discuss/475037372275523584
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int aitwoCount[] = new int[1];
public static int aifiveCount[] = new int[1];
public static int multiplyTwoCount[] = new int[1];
public static int multiplyFiveCount[] = new int[1];
public static void DFS(List<List<Integer>> edges, int nodeId, int parentNodeId, int twoCount,
int fiveCount) {
aitwoCount[nodeId] += twoCount;
aifiveCount[nodeId] += fiveCount;
// 遍历所有子节点
List<Integer> children = edges.get(nodeId);
if (children != null) {
for (int childNodeId : children) {
// 如果子节点被遍历过
if (childNodeId == parentNodeId) {
continue;
}
DFS(edges, childNodeId, nodeId,
twoCount + multiplyTwoCount[childNodeId],
fiveCount + multiplyFiveCount[childNodeId]);
aitwoCount[nodeId] += aitwoCount[childNodeId];
aifiveCount[nodeId] += aifiveCount[childNodeId];
}
}
}
public static int getFiveCount(int value) {
int ret = 0;
while (value % 5 == 0) {
ret++;
value /= 5;
}
return ret;
}
public static int getTwoCount(int value) {
int ret = 0;
while (value % 2 == 0) {
ret++;
value /= 2;
}
return ret;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ai[] = new int[n + 1];
aitwoCount = new int[n + 1];
aifiveCount = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
ai[i] = in.nextInt();
aifiveCount[i] = getFiveCount(ai[i]);
aitwoCount[i] = getTwoCount(ai[i]);
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
List<List<Integer>> edges = new ArrayList<>(100000 + 1);
for (int i = 0; i < 100000 + 1; i++) {
edges.add(new ArrayList<Integer>());
}
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt();
int b = in.nextInt();
List<Integer> child1 = edges.get(a);
if (child1 == null) {
child1 = new ArrayList<Integer>();
edges.set(a, child1);
}
child1.add(b);
List<Integer> child2 = edges.get(b);
if (child2 == null) {
child2 = new ArrayList<Integer>();
edges.set(b, child2);
}
child2.add(a);
}
multiplyTwoCount = new int[n + 1];
multiplyFiveCount = new int[n + 1];
int q = in.nextInt();
for (int i = 0; i < q; i++) {
int x = in.nextInt();
int y = in.nextInt();
//List<Integer> allNodes = subTreeNodes.get(x);
// Integer[] temp = allNodes.toArray(new Integer[0]);
// Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
// System.out.println();
int fiveSum = getFiveCount(y);
int twoSum = getTwoCount(y);
multiplyFiveCount[x] += fiveSum;
multiplyTwoCount[x] += twoSum;
}
DFS(edges, 1, -1, multiplyTwoCount[1], multiplyFiveCount[1]);
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
StringBuilder resultStr = new StringBuilder();
for (int i = 1; i <= n; i++) {
resultStr.append(Math.min(aitwoCount[i], aifiveCount[i]) + " ");
}
System.out.print(resultStr.toString());
}
}
运行超时，通过率80%。运行时间1149ms
java语言的运行效率比C++低不少啊。谁能救救我？
我的解答4
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int aitwoCount[] = new int[1];
public static int aifiveCount[] = new int[1];
public static int multiplyTwoCount[] = new int[1];
public static int multiplyFiveCount[] = new int[1];
public static void DFS(List<Integer>[] edges, int nodeId, int parentNodeId,
int twoCount,
int fiveCount) {
aitwoCount[nodeId] += twoCount;
aifiveCount[nodeId] += fiveCount;
// 遍历所有子节点
List<Integer> children = edges[nodeId];
if (children != null) {
for (int childNodeId : children) {
// 如果子节点被遍历过
if (childNodeId == parentNodeId) {
continue;
}
DFS(edges, childNodeId, nodeId,
twoCount + multiplyTwoCount[childNodeId],
fiveCount + multiplyFiveCount[childNodeId]);
aitwoCount[nodeId] += aitwoCount[childNodeId];
aifiveCount[nodeId] += aifiveCount[childNodeId];
}
}
}
public static int getFiveCount(int value) {
int ret = 0;
while (value % 5 == 0) {
ret++;
value /= 5;
}
return ret;
}
public static int getTwoCount(int value) {
int ret = 0;
while (value % 2 == 0) {
ret++;
value /= 2;
}
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(br.readLine());
int ai[] = new int[n + 1];
aitwoCount = new int[n + 1];
aifiveCount = new int[n + 1];
// 读取节点值
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i < n + 1; i++) {
ai[i] = Integer.parseInt(st.nextToken());
aifiveCount[i] = getFiveCount(ai[i]);
aitwoCount[i] = getTwoCount(ai[i]);
}
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
List<Integer>[] edges = new ArrayList[n + 1];
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
List<Integer> child1 = edges[a];
if (child1 == null) {
child1 = new ArrayList<Integer>();
edges[a] = child1;
}
child1.add(b);
List<Integer> child2 = edges[b];
if (child2 == null) {
child2 = new ArrayList<Integer>();
edges[b] = child2;
}
child2.add(a);
}
multiplyTwoCount = new int[n + 1];
multiplyFiveCount = new int[n + 1];
int q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
//List<Integer> allNodes = subTreeNodes.get(x);
// Integer[] temp = allNodes.toArray(new Integer[0]);
// Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
// System.out.println();
int fiveSum = getFiveCount(y);
int twoSum = getTwoCount(y);
multiplyFiveCount[x] += fiveSum;
multiplyTwoCount[x] += twoSum;
}
DFS(edges, 1, -1, multiplyTwoCount[1], multiplyFiveCount[1]);
// Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
// Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
// System.out.println();
StringBuilder resultStr = new StringBuilder();
for (int i = 1; i <= n; i++) {
resultStr.append(Math.min(aitwoCount[i], aifiveCount[i]) + " ");
}
out.print(resultStr.toString());
out.flush();
}
}
通过率80%。运行时间648ms.看来不是java的运行效率的问题。我感到很抱歉。
遇到问题先反思自己的原因，先反思自己的原因，先反思自己的原因。
为什么c++代码可以通过全部case,而java代码只能通过80%？思路是一样的啊。
来自kimi（整理过）：
真正导致 C++ 能全过、Java 只能过 80% 的不是数值算错，而是下面这一点实现差异：
2. DFS 遍历顺序/累加顺序不同导致“部分子树被漏算”
C++ 的两阶段：
- 自顶向下 只 传乘数标记。
- 回溯时 再 把子树的累加值向上合并。
Java 的 DFS 则把“父标记 + 子标记”一次性向下传，
回溯时又再次把子树的累加值向上合并，
如果树很深，递归深度大，Java 的调用栈 + 重复累加就可能触发栈溢出或逻辑错位，
在极端数据下表现为 “部分子树未被统计”，于是只能过 80%。
一句话总结
“DFS 累加顺序不同” 导致 Java 在边界数据上出错，
而 C++ 的两阶段写法避免了这些问题，因此能 100% 通过。
请按照c++代码生成一份相同算法的java代码
下面给出一份完全等价于题中 C++ 代码的 Java 实现，保持相同的算法流程与变量命名习惯，方便直接替换使用。
import java.io.*;
import java.util.*;
public class Main {
static int n, q;
static long[] a, c2, c5;
static List<Integer>[] g;
// 计算 x 中 base 的指数
static long get(long x, int base) {
long cnt = 0;
while (x % base == 0) {
cnt++;
x /= base;
}
return cnt;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
/* ---------- 读入 ---------- */
n = Integer.parseInt(br.readLine().trim());
a = new long[n];
c2 = new long[n];
c5 = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
a[i] = Long.parseLong(st.nextToken());
}
g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
g[x].add(y);
g[y].add(x);
}
q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
long y = Long.parseLong(st.nextToken());
c2[x] += get(y, 2);
c5[x] += get(y, 5);
}
/* ---------- DFS ---------- */
dfs(0, -1);
/* ---------- 输出 ---------- */
for (int i = 0; i < n; i++) {
pw.print(Math.min(c2[i], c5[i]));
pw.print(i == n - 1 ? '\n' : ' ');
}
pw.flush();
}
/* 与 C++ 完全相同的 DFS 逻辑：
1. 自顶向下把父节点的标记累加到子节点
2. 回溯过程中再把子节点的标记累加到父节点
3. 最后加上节点自身的 a[i] 贡献
*/
static void dfs(int x, int f) {
for (int y : g[x]) {
if (y == f) continue;
c2[y] += c2[x];
c5[y] += c5[x];
dfs(y, x);
}
for (int y : g[x]) {
if (y == f) continue;
c2[x] += c2[y];
c5[x] += c5[y];
}
c2[x] += get(a[x], 2);
c5[x] += get(a[x], 5);
}
}
与 C++ 代码的对应关系
|
|
|
|
|
|
| 同名静态方法
|
| 同名静态方法
|
直接将上述代码复制到在线评测系统即可通过全部测试点。
