2020kickstart d Beauty of tree
题意:
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
上一篇: 安卓基础学习 |周总结
推荐阅读
-
CodeForces 29D Ant on the Tree
-
cf D. Minimal Height Tree
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
[cf] 1401 D.Maximum Distributed Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
BZOJ 2648: SJY摆棋子(K-D Tree)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
BZOJ5462: [APIO2018] 新家(K-D Tree)
-
BZOJ 1941: [Sdoi2010]Hide and Seek(k-d Tree)
-
BZOJ 4520: [Cqoi2016]K远点对(k-d tree)