欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020kickstart d Beauty of tree

程序员文章站 2022-06-21 20:07:03
题意:a,b两个人, 分别在一棵节点数为n的有根树上,随机选择一个点,每x(y)个点(往根的方向)对一个节点染色,直到到达或超过根节点。问这棵树被染色的点的期望值。解题思路:首先有N*N个情况,每种情况下这棵树被染色的数目之和除以N*N就是要求的期望值所以问题就算如何统计每种情况染色数目之和暴力枚举每种情况肯定是不行的,可以换一个思路来想,去求每个点被选取后会染色多少个点。在一棵树上,假设p-x就是p下一步会染的点,那么r[p]=r[p-x]+1,只需要一遍dfs指定向下遍历就....

题意:

a,b两个人, 分别在一棵节点数为n的有根树上,随机选择一个点,每x(y)个点(往根的方向)对一个节点染色,直到到达或超过根节点。

问这棵树被染色的点的期望值。

 

解题思路:

首先有N*N个情况,每种情况下这棵树被染色的数目之和除以N*N就是要求的期望值

所以问题就算如何统计每种情况染色数目之和

暴力枚举每种情况肯定是不行的,可以换一个思路来想,去求每个点被选取后会染色多少个点。在一棵树上,假设p-x就是p下一步会染的点,那么r[p]=r[p-x]+1,只需要一遍dfs指定向下遍历就能求出每个点能染多少个点,但是有个问题,我们只能知道父节点,距离自己x个单位的祖先节点没法知道,肯定不能再套一个dfs去找,因为x可能是n,这样复杂度又是n^2了。我们可以维护一个队列que,头尾分别为head,tail, 存点的编号,向下递归的时候t当前节点入队(tail++),当tail-head>x的时候头出队(head++),回溯的时候tail-head<x的时候head--,之前的头重新入队。这样每次que[head]里存的都是距离自己x个单位的节点的编号了。

然后还有一个问题就是,会有重复染色的情况,就是a和b在某种情况下都对一个点染色了,我们统计下每个点会被a染色多少次(bra),被b染色多少次(brb),bra*brb就是a和b重复染这个点的情况, 减去就行。br的维护可以通过子树的点来求。因为每个点只会被子数上的点染色。br[p]=sum(br[q]+1,q-x=p)。

然后还有个情况是每个点被自己染色 和被a或b染色的情况重复了,这种情况有bra+brb次减去。

 

 

最后还有一个情况是a,b都选择了同一个点 这个情况也要减去,这种情况有n个。

所以最终染色数目是所有点的ra*n+rb*n-bra*brb-bra-brb加和-n

时间复杂度是O(n)。

#include <bits/stdc++.h>
#define ps push_back
using namespace std;
const int maxn=5e5+5;
vector<int>edg[maxn];
long long ra[maxn], rb[maxn], bra[maxn], brb[maxn];
int head, tail;
long long que[maxn];
void dfs(int now, long long r[maxn], long long br[maxn], long long d)
{
    que[tail]=now;
    if(tail-head>d)head++;
    if(tail-head==d)
    {
        r[now]=r[que[head]]+1;
    }
    else  //not enough p
    {
        r[now]=1;
    }
    tail++;

    for(int i=0; i<edg[now].size(); i++)
    {
        int to=edg[now][i];
        dfs(to, r, br, d);,,
    }
    
    tail--;
    if(tail-head<d && head>0)head--;
    if(tail-head==d)br[que[head]]+=br[now]+1;
//    cout<<head<<" "<<tail<<endl;
//    cout<<now<<" "<<r[now]<<" "<<br[now]<<endl;
    return;
}
void solve()
{
    long long n, a, b, x;
    cin>>n>>a>>b;
    for(int i=2; i<=n; i++){scanf("%lld", &x);edg[x].ps(i);}
    head=0, tail=0;
    dfs(1, ra, bra, a);
    head=0, tail=0;
    dfs(1, rb, brb, b);
    double ans=0, fz=1.0/(n*n);
    for(int i=1; i<=n; i++)
    {
        ans+=ra[i]*n;
        ans+=rb[i]*n;
        ans-=bra[i]*brb[i];
        ans-=(bra[i]+brb[i]);
    }
    ans-=n;
    printf("%.6f\n", ans*fz);
    for(int i=1; i<=n; i++)
    {
        ra[i]=rb[i]=bra[i]=brb[i]=0;
        edg[i].clear();
    }

}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    int t;
//    cout<<setprecision(7)<<0.1234567<<endl;
    cin>>t;
    for(int i=1; i<=t; i++){
        cout<<"Case #"<<i<<": ";
        solve();
    }

    return 0;
}

 

本文地址:https://blog.csdn.net/johsnows/article/details/107389590