{"id":290,"date":"2010-06-27T15:01:00","date_gmt":"2010-06-27T07:01:00","guid":{"rendered":"http:\/\/localhost\/?p=290"},"modified":"2010-06-27T15:01:00","modified_gmt":"2010-06-27T07:01:00","slug":"bonus_incentive_plan","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=290","title":{"rendered":"Bonus \u5956\u52b1\u8ba1\u5212"},"content":{"rendered":"\n

Bonus \u5956\u52b1\u8ba1\u5212<\/p>\n

Time Limit:3000MS Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n


<\/p>\n

Input <\/strong><\/p>\n

\u8bf7\u505a\u5230\u6587\u4ef6\u5e95\u7ed3\u675f,\u5bf9\u4e8e\u6bcf\u4e00\u7ec4\uff1a
\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570N\uff0c\u8868\u793a\u57ce\u5e02\u7684\u6570\u76ee\u3002
\u63a5\u4e0b\u6765\u7684N-1\u884c\uff0c\u6bcf\u884c\u5305\u542b2\u4e2a\u6574\u6570\uff0cAi\u3001Bi\uff0c\u8868\u793aAi\u548cBi\u95f4\u6709\u4e00\u6761\u53cc\u5411\u7684\u65c5\u884c\u901a\u9053\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u5bf9\u4e8e\u6bcf\u4e00\u7ec4\u6d4b\u8bd5\u6570\u636e\uff0c\u8f93\u51fa\u4e00\u884c\uff1a
\u4e3a\u4e00\u4e2a\u5b9e\u6570\uff0c\u8868\u793a\u5e73\u5747\u7684\u652f\u4ed8\u8d39\u7528\uff0c\u4fdd\u7559\uff08\u56db\u820d\u4e94\u5165\uff09\u81f3\u5c0f\u6570\u70b9\u540e6\u4f4d\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Hint <\/strong><\/p>\n

10%\u7684\u6570\u636e\u4e2dN \u2264 10\uff1b
30%\u7684\u6570\u636e\u4e2dN \u2264 100\uff1b
50%\u7684\u6570\u636e\u4e2dN \u2264 1000\u3002
100%\u7684\u6570\u636e\u4e2d2 \u2264 N \u2264 10000\uff0cT \u2264 10\uff0c1 \u2264 Ai\uff0cBi \u2264 N\uff0cAi\u2260Bi\u3002
\u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02\u4e4b\u95f4\u6709\u4e14\u53ea\u6709\u4e00\u6761\u8def\u5f84\uff08Path\uff09\u3002 <\/p>\n

<\/p>\n

Source <\/strong><\/p>\n

\u5317\u4eac2010
\u989d\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u96be\u5b9e\u9645\u4e0a\u8fd8\u662f\u633a\u6c34\u6ef4\u3002\u3002\u5173\u952e\u662f\u7ed9\u6bcf\u6761\u8fb9\u7684\u8fb9\u6743\u8d4b\u503c\u6210\u8fd9\u4e2a\u70b9\u88ab\u7a7f\u8fc7\u7684\u6982\u7387\u3002\u3002\u90a3\u4e48\u7b54\u6848\u5c31\u662f\u6240\u6709\u8def\u5f84\u957f\u5ea6\u7684\u5e73\u5747\u503c\u3002\u3002
Code\uff1a
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int inf=~0U>>1,maxn=10000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>::iterator it;
vector<int> E[maxn];
int n,Size[maxn];
double Ans,Sum[maxn];
void Clear()
{
    rep(i,maxn)E[i].clear();
}<\/p>\n

void AddEdge(int s,int t)
{
    E[s].pb(t);E[t].pb(s);
}<\/p>\n

bool Init()
{
    Clear();
    if(scanf("%d",&n)!=1)return false;<\/p>\n

    int s,t;
    rep(i,n-1)
    {
        scanf("%d%d",&s,&t);
        –s;–t;
        AddEdge(s,t);
    }<\/p>\n

    return true;
}
void Dfs(int x,int f)
{
    Size[x]=1;Sum[x]=0;
    tr(e,E[x])if(*e!=f)
    {
        Dfs(*e,x);
        Size[x]+=Size[*e];
    }
    tr(e,E[x])if(*e!=f)
    {
        double c=double(Size[*e])*(n-Size[*e])\/(n*(n-1)\/2);
        \/\/cout<<(*e)<<"<->"<<x<<":"<<c<<endl;
        Sum[x]+=Size[*e]*c+Sum[*e];
        Ans+=(Size[x]-Size[*e])*(Sum[*e]+c*Size[*e]);
    }
}<\/p>\n

void Solve()
{
    Ans=0;
    Dfs(0,-1);
    printf("%0.6lfn",Ans\/((n-1)*n\/2));
}
int main()
{
    \/\/freopen("in","r",stdin);
    while(Init())Solve();
}<\/p>\n

<\/p>\n

1.0000000.8888890.7500000.84000021 231 22 341 21 31 451 25 22 34 3 <\/p>\n","protected":false},"excerpt":{"rendered":"

Bonus \u5956\u52b1\u8ba1\u5212 Time Limit:3000MS Memory Limit:65536KTotal Submit:58 Accepted:16 Case Time Limit:1000MS Description Input \u8bf7\u505a\u5230\u6587\u4ef6\u5e95\u7ed3\u675f,\u5bf9\u4e8e\u6bcf\u4e00\u7ec4\uff1a \u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570N\uff0c\u8868\u793a\u57ce\u5e02\u7684\u6570\u76ee\u3002 \u63a5\u4e0b\u6765\u7684N-1\u884c\uff0c\u6bcf\u884c\u5305\u542b2\u4e2a\u6574\u6570\uff0cAi\u3001Bi\uff0c\u8868\u793aAi\u548cBi\u95f4\u6709\u4e00\u6761\u53cc\u5411\u7684\u65c5\u884c\u901a\u9053\u3002 Output \u5bf9\u4e8e\u6bcf\u4e00\u7ec4\u6d4b\u8bd5\u6570\u636e\uff0c\u8f93\u51fa\u4e00\u884c\uff1a \u4e3a\u4e00\u4e2a\u5b9e\u6570\uff0c\u8868\u793a\u5e73\u5747\u7684\u652f\u4ed8\u8d39\u7528\uff0c\u4fdd\u7559\uff08\u56db\u820d\u4e94\u5165\uff09\u81f3\u5c0f\u6570\u70b9\u540e6\u4f4d\u3002 Sample Input Sample Output Hint 10%\u7684\u6570\u636e\u4e2dN \u2264 10\uff1b 30%\u7684\u6570\u636e\u4e2dN \u2264 100\uff1b 50%\u7684\u6570\u636e\u4e2dN \u2264 1000\u3002 100%\u7684\u6570\u636e\u4e2d2 \u2264 N \u2264 10000\uff0cT \u2264 10\uff0c1 \u2264 Ai\uff0cBi \u2264 N\uff0cAi\u2260Bi\u3002 \u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02\u4e4b\u95f4\u6709\u4e14\u53ea\u6709\u4e00\u6761\u8def\u5f84\uff08Path\uff09\u3002 Source \u5317\u4eac2010\u989d\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u96be\u5b9e\u9645\u4e0a\u8fd8\u662f\u633a\u6c34\u6ef4\u3002\u3002\u5173\u952e\u662f\u7ed9\u6bcf\u6761\u8fb9\u7684\u8fb9\u6743\u8d4b\u503c\u6210\u8fd9\u4e2a\u70b9\u88ab\u7a7f\u8fc7\u7684\u6982\u7387\u3002\u3002\u90a3\u4e48\u7b54\u6848\u5c31\u662f\u6240\u6709\u8def\u5f84\u957f\u5ea6\u7684\u5e73\u5747\u503c\u3002\u3002Code\uff1a#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define tr(e,x) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/290"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=290"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/290\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}