Good Bye 2014 D. New Year Santa Network 图的邻接表存储不用vector，dfs，概率，期望，想法
题目链接：
http://codeforces.com/problemset/problem/500/D
题意：
有n(1e5)个城市和n-1条边，构成一棵树。
同时我们会有q(1e5)次修改操作
对于每次操作，我们把一条边的边权减小到w
每次操作之后，我们任意选3个点，问你这三个点之间3条路径的距离之和的期望是多少
思路：
http://blog.csdn.net/snowy_smile/article/details/50942412
首先，我们全部都不考虑顺序。n个点选出3个，方案数为C(n,3)
然后，我们不妨以1为树根，然后研究每条边。
我们可以通过dfs，得到每条边的上下各有多少个点。
假如说在一条边i的上面有up[i]个点，下面有dn[i]个点。
那么，我们就有C(up[i],1)*C(dn[i],2)+C(up[i],2)*C(dn[i],1)种方案选到这条边
于是，我们累计每条边被选中的方案*边权，再/=方案数，答案就出来啦！
然而，我这样算出来的答案有问题，只有实际答案的一半，为什么呢？
因为有C(up[i],1)*C(dn[i],2)+C(up[i],2)*C(dn[i],1)种方案选到这条边
而每个方案中，这个边权都被我们走了2次。于是最后再*2就可以啦
学习到了这种邻接表的存图方式:邻接表的存图方式(不用vector正常的方式),可以给每条双向边编号。这样就能够与最初给的边的编号联系起来【编号的边/2是真正的边的编号】，给每条边做额外的处理！ 这是vector做不到的。
1 memset(first,0,sizeof(first); 2 3 void add(int x,int y,int ww){ 4 s[++id] = y; 5 w[id] = ww; 6 nxt[id] = first[x]; 7 first[x] = id; 8 } 9 10 for(int z=first[u]; z; z=nxt[z]) // 这样遍历，也可以给first初始化为-1，z变成~z
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 2e5+10; 17 18 int n,id; 19 int up[maxn],dn[maxn],sz[maxn],first[maxn],nxt[maxn],s[maxn],w[maxn]; 20 double ans; 21 22 void add(int x,int y,int ww){ 23 s[++id] = y; 24 w[id] = ww; 25 nxt[id] = first[x]; 26 first[x] = id; 27 } 28 29 double C2(ll x){ 30 return x*(x-1)/2.0; 31 } 32 33 double C3(ll x){ 34 return x*(x-1)*(x-2)/6.0; 35 } 36 37 void dfs(int u,int fa){ 38 sz[u] = 1; 39 for(int z=first[u]; z; z=nxt[z]){ 40 int v = s[z]; 41 if(v == fa) continue; 42 dfs(v,u); 43 sz[u] += sz[v]; 44 int zz = z/2; // zz是真的边，z是双向边的编号，所以/2 45 dn[zz] = sz[v]; 46 up[zz] = n-sz[v]; 47 ans += (C2(up[zz])*dn[zz]+up[zz]*C2(dn[zz]))*w[z]; 48 } 49 } 50 51 int main(){ 52 cin >> n; id = 1; 53 for(int i=1; i<n; i++){ 54 int u,v,w; cin>>u>>v>>w; 55 add(u,v,w); 56 add(v,u,w); 57 } 58 59 ans = 0; 60 dfs(1,-1); 61 62 int q = read(); 63 for(int i=0; i<q; i++){ 64 int num,ww; cin>>num>>ww; 65 ans -= (C2(up[num])*dn[num] + up[num]*C2(dn[num])) * (double)(w[num*2]-ww); 66 w[num*2] = ww; 67 printf("%.10f\n",ans*2/C3(n)); 68 } 69 70 71 return 0; 72 }优质内容筛选与推荐>>
1、bootstrap3浏览器支持情况
2、在 Linux 上配置一个 syslog 服务器
3、在Bonobo服务器里创建Repository（库）
4、Day2：字典
5、django框架中的cookie与session