题意：一只蜗牛，它的房子在树上的某个叶子节点上，它要从树的根节点出发，寻找自己的房子。树的任意两个节点的距离为1，房子出现在每个叶子节点上的可能性一样。有的节点上有虫子，如果有虫子，虫子会告诉蜗牛它的房子是不是在这个节点为根的子树上。求蜗牛所走距离的最小期望。
如下图，如果蜗牛制定的策略先到2，再到5再到4，则由于房子地点的不确定，所以可能走的距离为1,4,6，所以期望为11/3。如果制定的策略是先到3,根据虫子的话判断去4和5还是去2，则可能走的距离为2,4,3，所以期望为9/3 = 3。可以证明，最小的期望即为3。
解法：首先，设叶子节点总数为tt，则肯定会有tt种情况，所以只需要求出所有情况下，找到房子所需要走的距离之和即可。
设le[x]表示以x为根的子树上叶子节点的个数；
设su[x]表示在以x为根的子树上，各种情况下找到房子所需走的距离之和；（0为根节点，su[0] / le[0]即为所求）
设fail[x]表示在以x为根的子树上，遍历整个子树没有找到房子又返回x节点所需要走的距离和。
则le[x] += le[v[i]]，v是x的子节点集合；
for (int i = 0; i < v.size(); ++ i) { su[x] += (fail[x] + 1) * le[y] + su[y]；fail[x] += fail[y] + 2;}（这个状态转移方程很精妙，多体会下，最好画个树手算模拟一下）
tag:树形dp, think, good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-20 10:39 4 * File Name: (good)DP-POJ-2057.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <vector> 11 12 using namespace std; 13 14 #define CLR(x) memset(x, 0, sizeof(x)) 15 #define PB push_back 16 17 int n; 18 bool w[1005]; 19 vector<int> v[1005]; 20 int le[1005], fail[1005], su[1005]; 21 22 bool cmp(int x, int y) 23 { 24 return (fail[x]+2)*le[y] < (fail[y]+2)*le[x]; 25 } 26 27 void init() 28 { 29 CLR (le); CLR (fail); CLR (su); CLR (w); 30 for (int i = 0; i < n; ++ i) 31 v[i].clear(); 32 33 int t1; 34 char s[10]; 35 for (int i = 0; i < n; ++ i){ 36 scanf ("%d%s", &t1, s); 37 if (s[0] == 'Y') w[i] = 1; 38 if (t1 != -1) v[t1-1].PB(i); 39 } 40 } 41 42 void dfs(int x) 43 { 44 if (!v[x].size()){ 45 le[x] = 1; 46 su[x] = 0; 47 fail[x] = 0; 48 return; 49 } 50 51 for (int i = 0; i < (int)v[x].size(); ++ i){ 52 dfs(v[x][i]); 53 le[x] += le[v[x][i]]; 54 } 55 56 sort (v[x].begin(), v[x].end(), cmp); 57 for (int i = 0; i < (int)v[x].size(); ++ i){ 58 int y = v[x][i]; 59 su[x] += (fail[x]+1)*le[y] + su[y]; 60 fail[x] += fail[y] + 2; 61 } 62 if (w[x]) fail[x] = 0; 63 } 64 65 int main() 66 { 67 while (scanf("%d", &n) != EOF && n){ 68 init(); 69 dfs(0); 70 printf ("%.4f ", (double)su[0] / le[0]); 71 } 72 return 0; 73 }