题解 cf1085d minimum diameter tree

树的直径的两个端点一定是叶子节点(当边权都为正时)，这个结论显然；

将每一条边分成两类，一类为叶子节点连接的边，设为$a$，另一类为没有叶子节点连接的边，设为$b$；

对于b，我们希望每条$b$对直径贡献尽量小，因为两条可能成为直径的边可能同时包含了$b$。所以将所有$b$的值设为$0$；

根据这个结论，我们将所有$s$均摊给每条$a$；


#define ll long long
using namespace std;
inline int (){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int cnt,r[300000];
int main(){
    int n=read(),m=read();
    for (int i=1;i<n;++i){
        int u=read(),v=read();
        ++r[u];++r[v];
    }
    for (int i=1;i<=n;++i)
        if (r[i]==1)
            ++cnt;
    printf("%.18lf",2*m*1.0/(cnt*1.0));
}

题解 cf1085d minimum diameter tree

近期文章

近期评论

标签

热门

文章归档

分类目录

功能