CF101D Castle

传送门

首先，一定要把所有点遍历一遍，这时答案应该是(frac{sum 某个点第一次被遍历的时间点}{n-1}quad)，而且每条边只能走两次，所以每次要遍历完某棵子树才能遍历其它子树。

考虑每次先递归处理子树，记(f_x=sum x子树内某个点第一次被遍历的时间点，g_x=w_{x,fa_x}+sum x 子树内边权)
显然(g_x=sum_{y是x的儿子quad}g_y) ; (f_x)的话，因为要将儿子以一定顺序遍历，因此某个儿子的贡献应该是(f_y+sz_y*(w_{(x,y)}+pre)(pre=sum前面的g_y*2))

我们要使得答案最小，先考虑只有两个儿子(a,b),如果儿子(a)在前面,$$f_x=f_a+sz_aw_{(x,a)}+f_b+sz_b(w_{(x,b)}+g_a2)$$,如果是(b)在前，则为$$f_x=f_b+sz_bw_{(x,b)}+f_a+sz_a(w_{(x,a)}+g_b2)$$现在如果(a)在前面答案更小,则$$f_a+sz_aw_{(x,a)}+f_b+sz_b(w_{(x,b)}+g_a2)<f_b+sz_bw_{(x,b)}+f_a+sz_a(w_{(x,a)}+g_b2)$$$$sz_aw_{(x,a)}+sz_b(w_{(x,b)}+g_a2)<sz_bw_{(x,b)}+sz_a(w_{(x,a)}+g_b2)$$$$sz_bg_a2<sz_ag_b2$$$$frac{g_a}{sz_a}<frac{g_b}{sz_b}$$

然后进行推广,把上式作为排序优先级,排序后做就能得出最终答案了

#include<bits/stdc++.h>
#define il inline
#define re register
#define LL long long
#define db double
#define eps (1e-7)

using namespace std;
const int N=500000+10;
il LL rd()
{
    LL x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
db w[N<<1];
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y,int z)
{
    ++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
    ++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;
}
int n;
struct nn
{
    db x,y,z;
    bool operator < (const nn &bb) const {return z/y!=bb.z/bb.y?z/y<bb.z/bb.y:z<bb.z;}
}st[N];
db f[N],g[N],sz[N];
void dfs(int x,int ffa)
{
    sz[x]=1;
    for(int i=hd[x];i;i=nt[i])
    {
        int y=to[i];
        if(y==ffa) continue;
        dfs(y,x);
        sz[x]+=sz[y];
    }
    int tt=0;
    for(int i=hd[x];i;i=nt[i])
    {
        int y=to[i];
        if(y==ffa) continue;
        st[++tt]=(nn){f[y]+sz[y]*w[i],sz[y],g[y]+w[i]};
    }
    sort(st+1,st+tt+1);
    for(int i=1;i<=tt;i++)
    {
        f[x]+=st[i].x+st[i].y*g[x]*2;
        g[x]+=st[i].z;
    }
}

int main()
{
    n=rd();
    for(int i=1;i<n;i++)
    {
        int x=rd(),y=rd(),z=rd();
        add(x,y,z);
    }
    dfs(1,0);
    printf("%.8lf
",f[1]/(db)(n-1));
    return 0;
}