【文件属性】：
文件名称：迷失游乐园NOI-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2021-04-25 05:25:10
动态规划
迷失游乐园（NOI2012）
给定一个n点、m条边的无向连通图。小Z随机从某个点出发，每次随机等概率地去一个和当前点有边的点，并且同一个点不去两次（包括起始点）。这个过程一直进行，直到当前点的所有相邻点都已经访问过为止。小Z所有经过的点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？
数据规模：
对50%的数据 ：m=n-1;
另外50%的数据，m=n,且环上点数不超过20;
100%的数据有n<=10^5。