一个有趣题。
看了题解不会证复杂度，结果被教练搞出另一个做法。
题目链接：easy
ver. hard
ver.
题意
现在有棵
个节点的有根二叉树，第
个点有一个容量 。两个人 A 和 B
在上面做游戏。
A 每一次会从这棵树的根(
号点)上投下一个球，每一个球都带一单位正电荷或负电荷。
每当一颗球下落到一个点时：
- 若该点左右两棵子树都满了，则这颗球停留在这个节点；
- 否则这个子树恰有一棵子树未满，则这颗球向那棵子树移动；
- 若两棵次数的电荷代数和不等，则按照电荷吸引规则移动；
- 否则由 B 选择移动方向。
若一个点
被填满，则游戏结束。
A 想要投下小球个数尽可能少，B 想要尽可能多。
两个人都绝对聪明，对于每一个 ，输出最终的游戏局数。
easy ver.：
hard ver.：
题解
easy ver.
通常遇到这种题，我们需要先寻找两个人的最优决策。
首先我们发现，若在某一时刻轮到 B 决策小球走向，那么 B
一定会让小球走到离点
即可能远的那棵子树。
而 A 在选择电荷的时候，一定是尽可能减少 B 的决策。（因为让 B 决策对 A
来说一定不会更优）
所以可以得到结论，A 的最优决策之一，是一直投正电荷；B
的最优决策，是一直将小球向离目标更远的地方放。
知道两人的决策，我们再来想如何统计答案。
对于点 ，我们想要知道的是，多少个球投下之后，点
这个子树内共被投进 个球。
当 时，答案显然，所以我们设
， 为 的另一个儿子。
容易发现，当第一个小球进入子树
时，B 一定会让这个小球到 ；第二个小球一定会到 ...
小球的去向会在
两棵子树内交替，直到 子树内有
个小球或 子树已经被填满。
那么这个问题就转化成：多少个球投下之后， 这个子树内共被投进 个球。
容易发现，这些问题都是：多少个球投下之后，点 这个子树内共有 个球 的形式。
而这个问题容易以如上递归的形式，在 的复杂度内被解决。
具体的，设当前我们需要
个小球，当前子树兄弟的 为 ，则令 即可。
所以我们这样就可以做到
的复杂度，并通过 easy ver.。
hard ver.
首先使用平衡树进行启发式合并可以很复杂地做到
的复杂度，这里就不仔细说了。
重新观察上面的式子：。
不难发现这样一些规律：
- 如果有 ，那么 ，这样 就会翻倍，这种情况做多会出现 次；
- 如果有 ，那么 ，如果有多个
都满足条件，那么他们可以快速计算贡献。
使用 表示， 点的所有祖宗中，最深的，满足兄弟的
的是哪一个祖宗（不存在则为 ）。
当我们计算 点中需要有 个球的答案时：
若 的兄弟的 ，则 ；
否则 ，取 ，我们可以快速计算 这一段贡献。
并且我们发现 兄弟的 （设为 ）有：。
令 即可。
其中 表示 的兄弟的 ，即兄弟 的祖先和。
而我们下一步会令 。
所以，每当我们向上跳一次，
就会变为原来的至少
倍。
所以时间复杂度为 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int st[1000001][62];
ll bro[1000001];
ll siz[1000001];
ll pre[1000001];
int f[1000001];
ll c[1000001];
int n;
inline int get(ll val)
{
int ans=-1;
for(int i=32;i;i>>=1) if(1ll<<(ans+i)<=val) ans+=i;
return ans;
}
inline void update(ll &val,int &ans)
{
while(val>=(1ll<<(ans+1))) ans++;
}
inline ll get(int p)
{
ll val=siz[p];int w=get(val);
while(p!=1)
{
if(val<=bro[p])
{
val*=2,w++,p=f[p];
continue;
}
int &num=st[p][w];
val+=pre[p]-pre[num];
p=st[p][w];
if(val>=bro[p]) val+=bro[p],p=f[p];
update(val,w);
}
return val;
}
int main()
{
n=lread(),bro[1]=inf;
for(int i=0;i<=61;i++) st[1][i]=1;
for(int i=2;i<=n;i++) f[i]=lread();
for(int i=1;i<=n;i++) c[i]=siz[i]=lread();
for(int i=n;i;i--) siz[f[i]]+=siz[i];
for(int i=2;i<=n;i++)
{
bro[i]=siz[f[i]]-c[f[i]]-siz[i];
pre[i]=pre[f[i]]+bro[i];
for(int j=0;j<=60;j++)
{
if(bro[i]<=(1ll<<j)) st[i][j]=st[f[i]][j];
else st[i][j]=i;
}
}
for(int i=1;i<=n;i++) printf("%lld ",get(i));
return 0;
}
|
感谢观看！