cf123E Maze

传送门

分析

见ptx大爷的博客

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int siz[100100],n;
vector<int>v[100100];
double Ans,a[100100],b[100100],tota,totb;
inline void dfs(int x,int fa){
    int i,j,k;
    siz[x]=1;
    for(i=0;i<v[x].size();i++)
      if(v[x][i]!=fa){
          dfs(v[x][i],x);
          siz[x]+=siz[v[x][i]];
          a[x]+=a[v[x][i]];
          Ans+=(double)a[v[x][i]]*siz[v[x][i]]*b[x];
      }
    Ans+=(double)(tota-a[x])*(n-siz[x])*b[x];
}
int main(){
    int i,j,k;
    scanf("%d",&n);
    for(i=1;i<n;i++){
      int x,y;
      scanf("%d%d",&x,&y);
      v[x].push_back(y);
      v[y].push_back(x);
    }
    for(i=1;i<=n;i++){
      scanf("%lf%lf",&a[i],&b[i]);
      tota+=a[i];
      totb+=b[i];
    }
    dfs(1,0);
    printf("%0.10lf
",Ans/tota/totb);
    return 0;
}