poj 1162 java

import java.util.Scanner;

public class POJ_1162 {

	static int n;
	static int head[];
	static W1 p[];
	static int f[];
	static int dp[][];
	static int num;
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		while(true){
			n = scan.nextInt();
			if(n == 0)
				break;
			head = new int[n+1];
			java.util.Arrays.fill(head, -1);
			p = new W1[n+1];
			f = new int[n+1];
			dp = new int[n+1][2];
			
			num = 0;
			
			for(int i=1;i<=n;i++){
				int u = scan.nextInt();
				if(u != -1)
					add(u,i);
				f[i] = scan.next().charAt(0)=='Y'?1:0;
			}
			
			double ans = dfs(1);
			System.out.printf("%.4f",(double)dp[1][1]/ans);
			System.out.println();
				
		}

	}

	public static int dfs(int u) {
		
		if(head[u]==-1)
			return 1;
		X po[] = new X[40];
		int H = 0,t = 0;
		
		for(int i=head[u];i!=-1;i=p[i].next){
			
			po[t] = new X(dfs(p[i].v),dp[p[i].v][0]+2);//dfs()求叶子结点个数,所有子树边*2
			dp[u][1] += dp[p[i].v][1]+po[t++].c;
			
		}
		
		java.util.Arrays.sort(po,0,t);
		
		for(int i=t-1;i>=0;i--){
			dp[u][1] += H*po[i].key;
			dp[u][0] += po[i].key;
			H += po[i].c;
		}
		if(f[u]==1)           //f[u]==1表示 此点有worm
			dp[u][0] = 0;        
		return H;
		
	}

	public static void add(int u, int v) {
		
		p[num] = new W1(v,head[u]);
		head[u] = num++;
		
	}
}
class W1{
	int v;
	int next;
	public W1(int v, int next) {
		super();
		this.v = v;
		this.next = next;
	}
	
}
class X implements Comparable<X>{
	int c;
	int key;
	public X(int c, int key) {
		super();
		this.c = c;
		this.key = key;
	}
	
	public int compareTo(X e) {
		if(this.key*e.c<this.c*e.key)
			return -1;
		else if(this.key*e.c>this.c*e.key)
			return 1;
		return 0;
	}
	
}