输入样例：
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例：
42.4解题思路：
求根结点到叶子结点的总权值，用dfs深搜可以递归当前结点的儿子，直到遇到叶子结点时累加权值，但Java的dfs有两个测试点过不去，同样的思路换成c++直接AC；bfs可以在出队时判断是否为叶子结点，并将权值累加；用dfs记忆化搜索当前结点的深度，递归时将搜到的结果都保存下来，最后遍历叶子结点将权值累加。
Java代码：（dfs）
import java.io.*;
import java.util.Arrays;
public class Main {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static int ini() throws IOException {
st.nextToken();
return (int)st.nval;
}
public static double ind() throws IOException {
st.nextToken();
return st.nval;
}
static int n, N = 100005, idx;
static double p, r, sum, t;
static int []h = new int[N];
static int []e = new int[N];
static int []ne = new int[N];
static int []w = new int[N];
public static void main(String[] args) throws IOException {
n = ini(); p = ind(); r = ind();
Arrays.fill(h, -1);
for(int i = 0; i < n; i++) {
int k = ini();
if(k != 0)
while(k-- > 0) add(i, ini());
else w[i] = ini();
}
dfs(0, 1);
System.out.printf("%.1f", sum);
}
public static void dfs(int u, int d) {
if(h[u] == -1) {
t = p * Math.pow(1 + 0.01 * r, d - 1);
sum += t * w[u];
}
for(int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j, d + 1);
}
}
public static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}
?
?
c++代码：（dfs)
#include <bits/stdc++.h>
const int N = 100005;
int n, idx;
int h[N], e[N], ne[N], w[N];
double p, r, sum, t;
void dfs(int u, int d){
if(h[u] == -1){
t = p * pow(1 + 0.01 * r, d - 1);
sum += t * w[u];
}
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j, d + 1);
}
}
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int main(){
scanf("%d%lf%lf", &n, &p, &r);
for(int i = 0; i < N; i++) h[i] = -1;
for(int i = 0; i < n; i++){
int k;
scanf("%d", &k);
if(k != 0)
while(k--) {
int x;
scanf("%d", &x);
}
else {
int x;
scanf("%d", &w[i]);
}
}
dfs(0, 1);
printf("%.1lf", sum);
return 0;
} 
?
?
Java代码：（bfs）
import java.io.*;
import java.util.*;
public class Main {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static int ini() throws IOException {
st.nextToken();
return (int)st.nval;
}
public static double ind() throws IOException {
st.nextToken();
return st.nval;
}
static int n, idx;
static double p, r;
static int N = 100005;
static int []e = new int[N];
static int []ne = new int[N];
static int []h = new int[N];
static int []w = new int[N];
public static void main(String[] args) throws IOException {
n = ini(); p = ind(); r = ind();
Arrays.fill(h, -1);
for(int i = 0; i < n; i++) {
int k = ini();
if(k != 0)
while(k-- > 0) add(i, ini());
else w[i] = ini();
}
if(n == 1) System.out.printf("%.1f", w[0] * p);
else bfs(0);
}
public static void bfs(int root) {
Queue<Integer> qu = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
qu.add(root);
int le = 0;
double sum = 0;
while(!qu.isEmpty()) {
le++;
if(le > 1) p = (1 + r * 0.01) * p;
while(!qu.isEmpty()) {
int t = qu.poll();
if(t != root && h[t] == -1) sum += w[t] * p;
for(int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
list.add(j);
}
}
qu.addAll(list);
list.clear();
}
System.out.printf("%.1f", sum);
}
public static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}
?
?
Java代码（dfs记忆化搜索）
import java.io.*;
import java.util.Arrays;
public class Main {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static int ini() throws IOException {
st.nextToken();
return (int)st.nval;
}
public static double ind() throws IOException {
st.nextToken();
return st.nval;
}
static int N = 100005;
static int []pa = new int[N];
static int []cnt = new int[N];
static int []f = new int[N];
public static void main(String[] args) throws IOException {
int n = ini();
double p = ind(), r = ind(), sum = 0;
Arrays.fill(pa, -1);
Arrays.fill(f, -1);
for(int i = 0; i < n; i++) {
int k = ini();
for(int j = 0; j < k; j++) {
pa[ini()] = i;
}
if(k == 0) cnt[i] = ini();
}
for(int i = 0; i < n; i++) {
if(cnt[i] != 0)
sum += p * Math.pow(1 + r * 0.01, dfs(i)) * cnt[i];
}
System.out.printf("%.1f", sum);
}
public static int dfs(int u) {
if(f[u] != -1) return f[u];
else if(pa[u] == -1) return f[u] = 0;
else return f[u] = dfs(pa[u]) + 1;
}
}
?
?
