求树上任意两点间距离之和

HDU2376 Average distance

求树上任意两点间距离之和：树有n个结点，对于一条边，假设连接的结点是u，v，u为父节点，设以v为根的子树共有x个结点，那么这条边对结果的贡献就是value*x*(n-x)，即这条边共被计算了x*(n-x)次！

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 10005;
struct edge{
    int from, to, next;
    ll val;
}e[maxn*2];
ll n, tot, ans;
int head[maxn], vis[maxn];
ll dfs(int x){
    vis[x] = 1;
    ll sons = 1;
    for (int i=head[x]; i; i=e[i].next) if (!vis[e[i].to]){
        ll tmp = dfs(e[i].to);
        sons += tmp;
        ans += tmp*(n-tmp)*e[i].val;
    }
    return sons;
}
inline void add(int from, int to, int val){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].val = val, e[tot].next = head[from];
    head[from] = tot;
    return;
}
inline int read(){
    int x=0;    char ch = getchar();
    while (ch<'0' || ch>'9')    ch = getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x;
}
int main(){
    int t, from, to, val;
    scanf ("%d", &t);
    while (t--){
        n = read(); tot = ans = 0;
        for (int i=1; i<=n; i++)    head[i] = vis[i] = 0;
        for (int i=1; i<n; i++){
            from = read()+1, to = read()+1, val = read();
            add(from, to, val); add(to, from, val);
        }
        dfs(1);
        printf ("%.6lf\n", (double)ans/(n*(n-1)/2));
    }
    return 0;
}

HDU6446 Tree and Permutation

求树上任意两点间距离之和，再乘上2*(n-1)!，就是答案。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+5, mod = 1e9+7;
struct edge{
    int from, to, next, val;
}e[maxn*2];
ll n, fac[maxn];
int head[maxn], tot, vis[maxn];
ll ans;
ll getSons(int x){
    vis[x] = 1;
    ll sons = 1;
    for (int i=head[x]; i; i=e[i].next) if (!vis[e[i].to]){
        ll tmp = getSons(e[i].to);
        ans = (ans+tmp*(n-tmp)%mod*e[i].val%mod)%mod;
        sons += tmp;
    }
    return sons;
}
inline void add(int from, int to, int val){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].val = val, e[tot].next = head[from];
    head[from] = tot;
    return;
}
void init(){
    fac[1] = 1;
    for (ll i=2; i<=100000; i++)   fac[i] = fac[i-1]*i%mod;
    return;
}
int main(){
    int from, to, val;
    init();
    while (~scanf ("%lld", &n)){
        ans = 0;
        tot = 0;
        for (int i=1; i<=n; i++)    head[i] = vis[i] = 0;
        for (int i=1; i<n; i++){
            scanf ("%d %d %d", &from, &to, &val);
            add(from, to, val); add(to, from, val);
        }
        getSons(1);
        printf ("%lld\n", ans*2*fac[n-1]%mod);
    }
    return 0;
}