expectation
Description
给出一棵带权值的树,我们假设从某个节点出发,到目标节点的时间为两个节点之间的最短路。由于出发节点不好选取,所以选在每个节点都有一定的概率,现在我们要求从出发点到目标节点的期望时间(即每个节点到目标点的时间*概率)。 为了避免精度错误, 直接给出了每个节点所占的权值, 那么每个节点的概率就是节点权值/总权值和( 注意查看实际输出要求)。
Input
输入第一行为一个正整数 n 表示树的节点数目, 节点编号从 1 到 n。
接下来一行 n 个整数 vi, 表示第 i 个节点所占的权值(<=20)。 紧接着 n-1 行,每行三个数 x, y, d (d<=20) ,表示经过 x 和 y 之间的树边 所需花费的时间为 d。
接下来一行有一个整数 q,表示询问数目。 紧接着 q 行, 每行一个整数,表示目的节点。
30%的数据: n<=20,q=1
50%的数据: n<=1000, q<=10
80%的数据: n<=10000,q<=1000 100%的数据: n<=100000, q<=n
Output
Sample Input
51 1 1 1 11 2 21 3 11 4 33 5 21 3
Sample Output
10
思路
每个节点保存两个值,一个是其子树的点权和(包括自身节点) nodesum[ ],一个是其子树各点到它的期望时间和 dp[ ]。那么我们假设根节点为 u ,其仅有一个儿子 v , u 到 v 的距离为 w ,而 v 有若干儿子节点,那么 dp[v] 表示 v 的子树各点到 v 的期望时间和,那么各个节点到达 u 的期望时间和便可以这样计算: dp[u] = dp[v] + nodesum[ v ] *w; (式子的理解,v 的一个儿子节点为 f,那么 f 到达 u 的期望时间为 (sum[ f ->v] + sum [v- > u])*val[f] (其中 val[v] 为 f 的权值),dp[v] 包含了 sum[f->v]*val[f],所以也就是式子的分配式推广到各个子节点计算出来的和),求出了 nodesum[ ] 数组和 dp[ ] 数组后,对于 q 个询问可以快速的求出。我们已经知道了各个节点到达根节点的期望时间和,那么从根节点开始递推下来可以得到各个点的期望时间和。另开一个数组表示每个节点的期望时间和,那么 dissum[u] = dp[u]。以 u 的儿子 v 为例, v 的子节点到 v 不必经过 v->u 这条路径,因此 dissum[u] 多了 nodesum[v] * w,但是对于不是 v 的子节点的节点,只到达了 u ,因此要到达 v 必须多走 u->v 这条路径,因此 dissum[u] 少了 ( totaval - nodesum[v] ) * w) ,所以 dissum[v] = dissum[u] - nodesum[v] * w + (total - nodesum[v] ) * w,按照这个方法递推下去就可以得到各个点的期望时间和。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 100005; struct Edge{ int u,v,w,next; }edge[maxn<<1]; int tot = 0,totval= 0,head[maxn],val[maxn],nodesum[maxn],dissum[maxn],dp[maxn]; void addedge(int u,int v,int w) { edge[tot].u = u,edge[tot].v = v,edge[tot].w = w,edge[tot].next = head[u]; head[u] = tot++; } void dfs1(int u,int fa) { int i; dp[u] = 0,nodesum[u] = val[u]; for (i = head[u];~i;i = edge[i].next) { int v = edge[i].v,w = edge[i].w; if (v == fa) continue; dfs1(v,u); dp[u] += dp[v] + nodesum[v]*w; nodesum[u] += nodesum[v]; } } void dfs2(int u,int fa) { int i; for (i = head[u];~i;i = edge[i].next) { int v = edge[i].v,w = edge[i].w; if (v == fa) continue; dissum[v] = dissum[u] - nodesum[v]*w + (totval - nodesum[v])*w; dfs2(v,u); } } int main() { //freopen("input.txt","r",stdin); int N,i,u,v,w,m,tmp; memset(head,-1,sizeof(head)); scanf("%d",&N); for (i = 1;i <= N;i++) scanf("%d",&val[i]),totval += val[i]; for (i = 1;i < N;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs1(1,1); dissum[1] = dp[1]; dfs2(1,1); scanf("%d",&m); for (i = 1;i <= m;i++) { scanf("%d",&tmp); printf("%d\n",dissum[tmp]); } return 0; }