题目pdf：
大致题意：
一棵树，一个人从A节点出发，等可能的选任何一条边走，有两个节点B，，C求这个人先到达B的概率
思路：
先说结论：只和离A的距离有关，先到达B+先到达A的概率 = 1，然后根据距离分配一下就好。
构造性证明：如果B-A-C在一条链上显然就是按距离分配概率，因为链上的支路对概率一点影响没有，因为假如走到支路上，你会发现，原本只是向前向后各1/2的概率现在不变成1/3了吗，并不是，一条链上的点往C或往B走的概率其实永远都是1/2，因为走到支路以后还要考虑这部分最后对概率的贡献，所以它必然会回到原链上，这部分可能性任然会各一半的分流到B或C或其他支路方向，最终等于没有支路，所以如果B-A-C在一条链上显然就是按距离分配概率
若不在一条链上，以A为根，A点始终要到达LCA(B,C) ,现在又变成了一条链了，结论仍成立。
标解是，dp[x]是从x点出发先到达B的概率，显然有dp[B] = 1,dp[C] = 0.
dp[u] = sum(dp[v])/cnt(相邻的节点数),可以列线性方程，然后高斯消元解得dp[A]
这样效率就大大降低了
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )#define rep(i,n) for ( int i=0; i< int(n); i++ )using namespace std;typedef long long ll;#define X first#define Y secondtypedef pair<int,int> pii;template <class T>inline bool RD(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void PT(T x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) PT(x / 10);putchar(x % 10 + '0');}const int N = 233;int n,A,B,C;vector<int> G[N];int dep[N];bool vis[N];int pa[N][20];void BFS(int root){memset(vis,0,sizeof(vis));dep[root] = 0;queue<int>q;q.push(root);pa[root][0] = root;vis[root] = 1;while(!q.empty()){int u = q.front(); q.pop();for(int i=1;i<20;i++) pa[u][i] = pa[pa[u][i-1]][i-1];foreach(it,G[u]){int v = *it;if(vis[v] == 0){vis[v] = 1;pa[v][0] = u;dep[v] = dep[u]+1;q.push(v);}}}}int LCA(int u,int v){if(dep[u] > dep[v]) swap(u,v);for(int det = dep[v]-dep[u],i = 0;det;i++,det >>= 1)if(det&1) v=pa[v][i];if(v == u) return v;for(int i = 20-1;i >= 0;i–)if(pa[u][i] != pa[v][i]) v = pa[v][i],u = pa[u][i];return pa[u][0];}int main(){while(scanf("%d%d%d%d",&n,&A,&B,&C) == 4){REP(i,n) G[i].clear();REP(i,n-1){int u,v;RD(u),RD(v);G[u].push_back(v);G[v].push_back(u);}BFS(A);int lca = LCA(B,C);int db = dep[B]-dep[lca];int dc = dep[C]-dep[lca];double ans = 0;if( db == 0) ans = 1;else if( dc == 0) ans = 0;else ans = dc/(double)(db+dc);printf("%lf\n",ans);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上帝助自助者。
