---
title: Codeforce 500 D. New Year Santa Network 解析(思維、DFS、組合、樹狀DP)
description: "Codeforce 500 D. New Year Santa Network 解析(思維、DFS、組合、樹狀DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 500 D. New Year Santa Network 解析(思維、DFS、組合、樹狀DP)">
<!-- toc -->

# Codeforce 500 D. New Year Santa Network 解析(思維、DFS、組合、樹狀DP)
今天我們來看看CF500D
[題目連結](https://codeforces.com/problemset/problem/500/D)

> **題目**
給你一棵有邊權的樹，求現在隨機取$3$點，求這三點互相距離總和的期望值。

### 前言
今天寫的題目都是看解答就會寫，原本就沒有的自信心又要更低了

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
$3$個點要考慮的事情太多了，首先只要注意到以下一件事，那麼其他的事情就和[CF1401D](https://www.cnblogs.com/petjelinux/p/13546805.html)沒兩樣了。
注意到($E(X)$代表$X$事件的期望值):$E(d(c_1,c_2)+d(c_2,c_3)+d(c_1,c_3))=E(d(c_1,c_2))+E(d(c_2,c_3))+E(d(c_1,c_3))$
且$c_1,c_2,c_3$都是$dummy\ variable$,所以$E(d(c_1,c_2))=E(d(c_2,c_3))=E(d(c_1,c_3))$
也就是說我們只要能算出隨便取兩點的距離期望值，那麼最後答案$\times3$就好。

(以下內容可以參照[CF1401D](https://www.cnblogs.com/petjelinux/p/13546805.html))
那麼我們只要算出如果所有點對的距離都被算一次，每個邊會被算幾次就好。
維護每個子樹有幾個點為$cnt[v]$，接著枚舉邊$\{u,v,w\}$，保證$dep[u]<dep[v]$，這個邊會被走過的次數就是這條邊**連接**的兩個點集的點的數量的相乘，也就是$cnt[v]\times(n-cnt[v])$。把邊權總和儲存到一個$long\ long$裡，由於邊權總和至多是$n\times n^2\times1000=10^{18}$(1000是一條邊的最大邊權)，所以儲存沒有問題。
每次修改邊就單純的把這條邊的貢獻重算一遍就好。

### 程式碼:

const int _n=1e5+10;
int t,n,a,b,l,q,r,w,fa[_n],cnt[_n],dep[_n];
ll sum;
vector<PII> G[_n];
struct E{int u,v,w;} e[_n];
ll C(ll x){if(x<2ll)return 0;return x*(x-1)/2ll;}
void dfs(int v,int faa,int d){
  fa[v]=faa,dep[v]=d,cnt[v]=1;
  rep(i,0,SZ(G[v]))if(G[v][i].fi!=faa)
    dfs(G[v][i].fi,v,d+1),cnt[v]+=cnt[G[v][i].fi];
}
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,1,n){cin>>a>>b>>l;a--,b--;G[a].pb({b,l}),G[b].pb({a,l});e[i]={a,b,l};}
  dfs(0,-1,0);rep(i,1,n){
    int u=e[i].u,v=e[i].v,w=e[i].w;
    if(dep[u]>dep[v])swap(u,v);
    sum+=1ll*cnt[v]*(n-cnt[v])*w;
  }
  cin>>q;while(q--){
    cin>>r>>w;int u=e[r].u,v=e[r].v;
    if(dep[u]>dep[v])swap(u,v);
    sum-=1ll*cnt[v]*(n-cnt[v])*e[r].w;
    sum+=1ll*cnt[v]*(n-cnt[v])*w;
    cout<<setprecision(20)<<3.0*sum/(1.0*C(n))<<'\n';
    e[r].w=w;
  }
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/500/submission/91585122)