P5129

· · 题解

真是很有意思的一道题呢 虽然我交了一页才过

首先呢看到 n \leq 300000 ，那么枚举每条路径是肯定要 T 飞的。

那么既然是计算期望路径长，不能枚举每条路径，那就把路径拆开，我们来依次枚举每条边会被经过多少次。

还有为了方便，我们可以先算出总路径长再除以方案总数来算期望长度。

有了这些就可以开干了。

题上说有 n 个点 n 条边，那就是基环树，那我们就把在环边和非环边分开来看。

非环边的经过次数应该很好算，次数这条边两侧的点数量之积再乘以 2 。为什么呢，假如这条边一侧有 a 个点，另一侧是有 b 个点，那么如果要经过这条边，那就是要从一侧到另一侧去（假如起点和终点都在同一侧的话那为什么还要经过这条边呢）所以一共有 a\times b 条路径是要经过这条边的，然后又因为假如把起点和终点对调是算两条路径的所以要乘个 2 。

那么非环边对答案的贡献就是 sum_{left} \times sum_{right} \times 2 \times w_i 。

首先我们要明白一个道理：假如一条路径经过了环上任意一点，那么一定是存在另一条路径的。

（这也是这道题一个大坑：假设我们要从 4 到 1 ，那么其实是有两条路的：

）

那么这两条路径的长度分别是：

（假设起点是 a 终点是 b）

它们一起对答案的贡献是：（由于在 a 到 b 的方案中，两条路径的被选择概率都是 \frac{1}{2} ，所以要除一个 2）

(2 \times$ $a$ 到环的距离 $+$ 环的长度 $+$ $2\times b$ 到环的距离$) \div 2

而我们这里只关注环边的贡献，那么环边的贡献也就是：

环的长度 \div 2

那么我们可以推测出：假设有一个起点和终点之间的路径会经过环，那么环边一定会贡献环的长度 \div 2 的贡献。

那么我们就可以算出到底有多少种方案会经过环，再把方案数乘上这个贡献，就是环边的所有贡献了。这里呢先算有多少种方案不经过环再从总方案里扣除比较好算，而一个方案不经过环，那么起点和终点一定满足：

在同一棵子树内；

公共祖先不在环上。

说的简单明了，就是起点和终点一定要在环上的点的同一棵子树内：（如果在环上的点的两颗子树内，那么一定会经过环上的那个点）

那么，同一棵子树里的点两两之间可以产出一条不经过环的路径，那么总路径就是 x^2 条 ,其中 x 是子树大小；

那么有多少条路径不经过环也就可以算了，也就是所有子树的大小平方之和：

x_1^2+x_2^2+ \dots x_n^2

那么有多少条路径经过环也就可以算了，那么环边做出的总贡献也就可以算了：（length 是环的长度）

length\times(n^2-\sum\limits_{i=1}^nx_i^2)

然后两种边的贡献就算完了，加起来再除以方案总数，完——

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fi[10000001],nx[10000001],to[10000001],co[10000001],tot,length;
int n;
int loop[10000001],num,size[10000001];
int size_tree;
bool check[10000001],in[10000001],huan;
long long all;
stack<pair<int,int> >sta;
namespace Mod {
    const int mod = 19260817;
    int add(int x, int y) {
        return (x += y) < mod ? x < 0 ? x + mod : x : x - mod;
    }
    int Add(int&x, int y) {
        return (x += y) < mod ? x < 0 ? (x += mod) : x : (x -= mod);
    }
    int mul(int x, int y) {
        return 1LL * x * y % mod;
    }
    int Mul(int&x, int y) {
        return x = 1LL * x * y % mod;
    }
    int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1) {
            if (y & 1) Mul(res, x);
            Mul(x, x);
        }
        return res;
    }
    int inv(int x) {
        return qpow(x, mod - 2);
    }
}
using namespace Mod;
void link(int a,int b,int c)
{
    nx[++tot]=fi[a];
    fi[a]=tot;
    to[tot]=b;
    co[tot]=c;
} 
void dfs1(int now,int fa,int w)
{
    if(in[now])
    {
        length+=w;
        while(sta.top().first!=now)
        {
            loop[++num]=sta.top().first;
            length+=sta.top().second;
            check[sta.top().first]=1;
            sta.pop();
        }
        loop[++num]=now;
        check[now]=1;
        huan=1;
        return;
    }
    sta.push({now,w});
    in[now]=1;
    for(int i=fi[now];i;i=nx[i])
    {
        int v=to[i];
        if(v!=fa)
        {
            dfs1(v,now,co[i]);
            if(huan)
            {
                return;
            }
        }
    }
    sta.pop();
}
void dfs2(int now,int fa,int w)
{
    size[now]=1;
    for(int i=fi[now];i;i=nx[i])
    {
        int v=to[i];
        if(check[v]||v==fa)
        {
            continue;
        }
        dfs2(v,now,co[i]);
        size[now]+=size[v];
        if(check[now])
        {
            Add(size_tree,mul(size[v],size[v]));
        }
    }
    Add(all,mul(w,mul(2,mul(size[now],n-size[now]))));
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        link(x,y,z);
        link(y,x,z);
    }
    dfs1(1,0,0);
    for(int i=1;i<=num;i++)
    {
        dfs2(loop[i],0,0);
    }       
    Add(all,mul(mul(add(mul(n,n),-size_tree),length),inv(2)));
    cout<<mul(all,inv(mul(n,n)))<<endl;
}