http://poj.org/problem?id=1202

难度集中在输出格式上,因为输出格式所以是高精度

递推式:

血缘肯定只有从双亲传到儿子的,所以,设f,m为双亲,son为儿子,

p[i][j]为i和j之间的血缘关系,p[j][i]=p[i][j]

则:

p[son][f]=p[son][m]=0.5+0.5*p[f][m]

对于兄弟和其他不是双亲的节点j,则有

p[son][j]=0.5*(p[f][j]+p[m][j])

另外:http://swerc.up.pt/2002/Data/有数据

代码交了好几次都是RE,突然交了一次居然AC了

import java.math.BigDecimal;import java.util.*;class mes{	int son,nxt;	mes(){son=nxt=0;}}public class Main {	final static int maxn=650;	static int head[];	static BigDecimal p[][];	static mes s[];	static int fa[][];	static int n,k,m;	static int vis[];	static int que[];		static void addedge(int f,int t,int ind)	{	    s[ind].nxt=head[f];	    s[ind].son=t;	    head[f]=ind;	}	static Scanner scanner;	static void init()	{		for(int i=0;i
     
      0&&ans.indexOf(".")
      
       1&&ans.endsWith("0")){					ans=ans.substring(0,ans.length()-1);				}			}			if(ans.endsWith(".")&&ans.length()>1)ans=ans.substring(0,ans.length()-1);			System.out.println(ans+"%");		}	}	public static void main(String[] args) {		head=new int[maxn];		p=new BigDecimal[maxn][maxn];				s=new mes[2*maxn];		fa=new int[maxn][2];		que=new int[maxn];		vis = new int[maxn];		for(int i=0;i