CF1087D Minimum Diameter Tree

Posted by

http://codeforces.com/contest/1087/problem/D 分析:这道题贼毒瘤,看起来是一个找树的直径的玩意。仔细分析发现正解居然如此简单。 把边权分给出度为0的点,其他边不分,即可。最后\times 2即可。 比赛的时候没想出来嘤嘤嘤,rating直线下降啊qwq。。。

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
static const int MAXN=2000050;
using namespace std;
int n,sum,u,v,ans,vis[MAXN];
inline int read()
{
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main()
{
    n=read();sum=read();
    for(int i=1;i<=n-1;i++)
    {
        u=read();v=read();
        vis[u]++;vis[v]++;
    }
    for(int i=1;i<=n;i++) if(vis[i]==1) ans++;
    printf("%.10f\n",2.0*sum/ans);
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注