十二省联考2019 游记 & 题解

口中喊着「僕勝つから。ぜったい、勝て来るから。」的你,真的付出了桐山般的努力吗?

Day -1

晚上看 WF 直播,为了看滚榜睡得很晚,结果最后滚的时候 b 站那几个直播的去海底捞吃火锅,然后断断续续的….最后也没有看完滚榜,还是第二天才看的排名…

Day 0

由于前一天睡得比较晚,所以下午睡了两个小时。晚上 vp 了一场 cf。

然后..本来想早点睡,结果由于下午睡了两个小时,睡不着了..最后很晚才睡。在床上看了四集半《三月的狮子》..(半是因为看困了,于是赶紧抓住机会睡了。)

Day 1

早上起来的时候感觉特别清醒,后来才想起来,初三有段时间也不怎么睡,也是刚起来的时候并不会很困..走起路来有种 ふわふわ 的感觉..一直持续到快到华科的时候,才稍微觉得有点困..

拿到题之后看了眼 T1,异或 $\rightarrow$ 可持久化 01 Trie,求前 $k$ 大之和 $\rightarrow$ 分成 $n$ 类每类的最大值塞堆里。大致的思路真的是一眼就想出来了..然而并没有想到三元组的做法,虽然 18 年暑假去安师大附中集训的时候做过一道那样的题..

我想的做法是记录在 Trie 上 dfs 到的位置,然后根据位置求下一个。一开始我写的是每个点记录父亲,然后写+调 $2h$ 才想起来:这是可持久化啊,怎么记录父亲…然后尝试加了个 map 来记录不同版本的父亲,变成 $\log^2$,然后大样例跑了 $13s$,还 WA…

于是就先把 T1 放了一下,去看 T2。这 T2 什么鬼题面?(赛后结合讲题 PPT 里的简述一下就明白题意了,可能是简述的原因,也可能是没睡好考场上 sb 了..只不过一个没有题目背景的题为什么不写简述题意呢..)看了半天稍微看懂题意了,然后一看第一档暴力,好像第一档就得写个 $20min$ ~ $0.5h$ 的..我的习惯是先写 PJ 难度暴力,然后写正解,最后写不好写的部分分,所以就先放着了。

然后去看 T3..没想到竟然能在考场上碰到 ydc 的题面..先把 998244353 切了,然后写了个从最大值起枚举模数,然后..1145141?唐 突 恶 臭,//echouctr 警告。赛后得知有人直接(抱着恶臭的想法)试出来了..还有只枚举质数的..想不明白为什么要给个质数..搞的我还写了扩展欧拉定理和求 $\varphi$(虽然也没有太麻烦..)。1_?+ 直接弃了。wa 尝试把快速幂里的 long long 去掉,然后没过,就也弃了。后面的..猜到了 p 是质数,根据 0/+/- 猜到了 u 是 $\mu$,猜到了 g 是原根..nmdwsm是区间筛啊..

回来看 T1,重构的决定还算比较果断,换了种找后继的方式:记录 dfs 路径以及每个点被搜到的次数,满了就换个儿子,否则按原路径往下。写的还算比较顺利,不到 $1h$ 就过了大样例,然后开始对拍,也过拍了。然后,把 rand() 的范围开到 unsigned..不过拍了??检查了一下,所有该开 unsigned 的地方都开了,于是把所有参与位运算的 1 都改成了 1u,还是过不了..然后我就开始 sb 了:先把 unsigned int 改成 unsigned long long,发现过不了,然后改回 unsigned int,再把循环的范围从 31 改成 32.. 然后我就各种检查,直到考试结束也没过拍..考后发现,是一种边界情况的一行代码放错位置了,除了同时开 unsigned long long 和循环范围 32,也可以把那行代码换个位置来解决。

下午得知正式选手好像必须参加讲题?看分,发现第一题竟然过了..脸挺好的。T2 puts("-1") 果然没分。T3 写多少是多少(废话,这种题..)。$100+0+19$,$rk6$,被吊锤了..在其他省就垫底了..

晚上打了场 Global,神仙 Div.2 A~C & Div.1 E/F 场..写完 A ~ E 之后发现所有人包括 tourist 都是五题,而且 tourist 在我之前半个小时就写完五题了..于是就不想打了。又过了快一个小时,发现有好多人在 hack A,于是就去看了下,hack 了一个写法奇怪的 A。最后涨了不少分..

还好晚上顺利睡着了..

Day 2

由于昨天调 T1 调的心态爆炸才去看后面的题导致整场爆炸,于是这次先看了每道题..

看了看 T1,除了 dp 没啥想法,先写了个 $20$ 分暴力,准备把 dp 留到后面写。真的是 sb 了,没想到可以压两维,只压了一维..

然后去看 T2,第一眼并没有什么想法..暴力连第二档都不太会写,于是先写了个 $\mathcal O(n^n)$。

然后去看 T3,emm..暴力怎么写啊.webp。

然后去上了个厕所。在厕所里想到了 T2 的做法..写的比较顺利,大概不到 $1h$ 吧..就第一次测挂了,改了个小地方就过了所有样例。然后对拍,也过拍了。然后测了下链..RE了??冷静了一下,猜测是爆栈了,直接去问了监考,答复是栈空间和内存限制一样,然后就愉快地本地开栈过了。

然后去写 T1 的 dp..一开始尝试单数组滚动,然后挂了。于是改成 01 滚动,又调了好久才过..

最后去写 T3,决定只写 $k=1$。先写了下 $k=1$ & $l=n$ 的 dp,很快就写完了。然后去写剩下的 $k=1$,算了下复杂度,$\mathcal O(nl^2)$,感觉好悬..然后发现可以用 NTT 优化到 $\mathcal O(nl\log l)$,然后开始写 NTT,然后..NTT 没调出来..考前应该写一写的..因为比较头铁,NTT 一直调到了离考试结束 $15min$,然后开始 rush $\mathcal O(nl^2)$,失败了..

出考场不久,想起来自己 T1 好像忘清空了..辣鸡温馨提示。然后我在影响正确性/不影响正确性之间反复切换了几次结论..最后在看成绩之前得出的结论是,我没有限制($k=0$)的点稳挂,剩下的点大概率挂。

去看成绩,$20+100+8$。T1 竟然有 $20$?难道是 $k\ne0$ 的点都过了?听完讲题之后去看评测结果,发现是 $k=0$ 的两个点过了…至今没想明白,只不过如果清空了数组就是 $40$ 了。

最后是两天总分第四(和去年一样,白学了),加上 NOIP 还是被胡队爆踩了..

晚上两天挂分 $100+$ 的罗队在裙里问为什么 D2T2 $75​$ 分,我把他的代码复制到 LOJ 发现过了..

冷静了一下,感觉不可能是 OJ 的问题,所以不开 C++11 测了一下,果然没过..因为前几天写 OI Wiki 的时候查过,所以很快就猜到了,是 swap 的问题.. priority_queueswap 在不开 C++11 时是 $\mathcal O(n)$ 的。

题解

D1T1

考场做法

建可持久化 01 Trie,把区间异或和转化成两个前缀异或和的异或,然后对每个右端点就可以找到最大的异或和,扔进堆里。找最大值的时候记录一下在 Trie 上的路径,以及每一层经过的次数。堆里弹出一个值后插入下一个值时根据记录的路径来找:如果经过次数大于子树当前节点的 siz 就换个儿子并清空比他更深的节点的记录的经过次数,否则按记录的路径走。如果 Trie 的根都满了就不 push 了。

参考代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cctype>
#include <algorithm>

using namespace std;

int n,k;

typedef unsigned int ui;
typedef pair<ui,int> pui;

ui read()
{
ui out=0;
char c;
while (!isdigit(c=getchar()));
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out;
}

const int N=500010;

struct Node
{
int val,ch[2];
} t[N*35];

int rt[N],tot,d[N][35],cnt[N][35];
ui pre[N];
unsigned long long ans;
priority_queue<pui> q;

int ins(int x,ui y)
{
int i,u,v,root;
u=root=++tot;
t[u].val=t[x].val+1;
for (i=31;i>=0;--i)
{
v=((y>>i)&1u);
t[u].ch[v^1]=t[x].ch[v^1];
u=t[u].ch[v]=++tot;
x=t[x].ch[v];
t[u].val=t[x].val+1;
}
return root;
}

signed main()
{
scanf("%d %d",&n,&k);

int i,j,u,v,r;
ui x;

for (i=1;i<=n;++i)
{
pre[i]=pre[i-1]^read();
u=rt[i]=ins(rt[i-1],pre[i-1]);
for (x=0,j=31;j>=0;--j)
{
v=(((pre[i]>>j)&1u)^1u);
if (t[u].ch[v])
{
x|=(1u<<j);
d[i][j]=u=t[u].ch[v];
}
else d[i][j]=u=t[u].ch[v^1];
++cnt[i][j];
}
q.push(pui(x,i));
}

while (k--)
{
ans+=q.top().first;
r=q.top().second;
q.pop();
x=0;
for (u=rt[r],i=31;i>=0;--i)
{
v=(((pre[r]>>i)&1u)^1u);
if (cnt[r][i]==0)
{
++cnt[r][i];
if (t[u].ch[v])
{
x|=(1u<<i);
u=d[r][i]=t[u].ch[v];
}
else u=d[r][i]=t[u].ch[v^1];
}
else if (cnt[r][i]<t[d[r][i]].val)
{
if (d[r][i]==t[u].ch[v]) x|=(1u<<i);
++cnt[r][i];
u=d[r][i];
}
else
{
for (j=i;j>=0;--j) cnt[r][j]=0;
++cnt[r][i];
u=d[r][i]=t[u].ch[v^1];
}
}
if (cnt[r][31]==t[rt[r]].val) continue;
q.push(pui(x,r));
}

printf("%lld\n",ans);

return 0;
}

题解做法

除了找后继都是差不多的,找后继的方法是找完 $[0,r)$ 之后把 $[0,ans)$ 和 $(ans,r)$ 塞进堆里。

正常人做法

翻了下 LOJ 最短解,然后被自己蠢哭了..

直接记录每个右端点已经找到第 $k$ 大了,然后找第 $k$ 大的方式类似值域线段树/平衡树找第 $k​$ 大…

D1T2

讲一下 SAM 做法.. sb 选手不适合打 SA。

把所有串翻转,B 是 A 的前缀就变成了 B 是 A 的后缀。

是后缀就是 parent 树上的祖先,或者同一个节点且 len 更小。

把所有 A/B 串对应的节点按在 A/B 中的 len 拆点,每个 parent 树上的节点从较小的 len 向较大的 len 连边,A 串对应的点 & len 向 A 串连边,B 串向对应的点 & len 连边。

然后拓扑排序/记忆化搜索即可。

当然如果你像我一样 sb,可以按 dfs 序用线段树优化连边,就可以(假装)不用拆点了..

参考代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

int read()
{
int out=0;
char c;
while (!isdigit(c=getchar()));
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out;
}

const int N=200010;

struct Node
{
int len,par,ch[26];
} sam[N<<1];

void insert(int x);

int p,tot,fa[N<<1][20],sta[N];

void add(int u,int v);
long long dp(int u);

int head[N*5],nxt[N*6],to[N*6],cnt;
int n,na,nb,m,a[N],alen[N],b[N],blen[N],w[N*5],tot2;
set<int> aln[N<<1],bln[N<<1];
map<int,int> aid[N<<1],bid[N<<1];
long long ans,f[N*5];
bool vis1[N*5],vis2[N*5],loop;
char s[N];

int main()
{
int i,j,l,r,u,pre,T;

T=read();

while (T--)
{
scanf("%s",s+1);
n=strlen(s+1);
reverse(s+1,s+n+1);

for (i=1;i<=2*n;++i)
{
memset(sam[i].ch,0,sizeof(sam[i].ch));
aln[i].clear();
aid[i].clear();
bln[i].clear();
bid[i].clear();
}
memset(w,0,sizeof(w));
memset(head,0,sizeof(head));
memset(vis1,false,sizeof(vis1));
memset(vis2,false,sizeof(vis2));
cnt=ans=0;
p=tot=1;
loop=false;

for (i=1;i<=n;++i)
{
sta[i]=tot+1;
insert(s[i]-'a');
}

for (i=2;i<=tot;++i) fa[i][0]=sam[i].par;
for (j=1;j<=18;++j)
{
for (i=2;i<=tot;++i)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}

na=read();

for (i=1;i<=na;++i)
{
r=n+1-read();
l=n+1-read();
u=sta[r];
for (j=18;j>=0;--j)
{
if (sam[fa[u][j]].len>r-l)
{
u=fa[u][j];
}
}
a[i]=u;
alen[i]=r-l+1;
aln[u].insert(alen[i]);
bln[u].insert(alen[i]);
}

nb=read();

for (i=1;i<=nb;++i)
{
r=n+1-read();
l=n+1-read();
u=sta[r];
for (j=18;j>=0;--j)
{
if (sam[fa[u][j]].len>r-l)
{
u=fa[u][j];
}
}
b[i]=u;
blen[i]=r-l+1;
bln[u].insert(blen[i]);
}

tot2=tot;

for (i=2;i<=tot;++i)
{
if (bln[i].empty()) add(sam[i].par,i);
else
{
for (auto k : aln[i]) w[aid[i][k]=++tot2]=k;
pre=sam[i].par;
for (auto k : bln[i])
{
add(pre,bid[i][k]=++tot2);
if (aln[i].find(k)!=aln[i].end()) add(tot2,aid[i][k]);
pre=tot2;
}
add(tot2,i);
}
}

m=read();

for (i=1;i<=m;++i)
{
l=read();
r=read();
add(aid[a[l]][alen[l]],bid[b[r]][blen[r]]);
}

for (i=1;i<=na;++i) ans=max(ans,dp(aid[a[i]][alen[i]]));

if (loop) puts("-1");
else printf("%lld\n",ans);
}

return 0;
}

long long dp(int u)
{
if (vis2[u]) return f[u];
if (vis1[u]) loop=true;
if (loop) return 0;
vis1[u]=true;
int i,v;
f[u]=w[u];
for (i=head[u];i;i=nxt[i])
{
v=to[i];
f[u]=max(f[u],dp(v)+w[u]);
}
vis2[u]=true;
return f[u];
}

void insert(int x)
{
int np=++tot;
sam[np].len=sam[p].len+1;
while (p&&!sam[p].ch[x])
{
sam[p].ch[x]=np;
p=sam[p].par;
}
if (!p) sam[np].par=1;
else
{
int q=sam[p].ch[x];
if (sam[q].len==sam[p].len+1) sam[np].par=q;
else
{
int nq=++tot;
sam[nq].len=sam[p].len+1;
memcpy(sam[nq].ch,sam[q].ch,sizeof(sam[q].ch));
sam[nq].par=sam[q].par;
sam[q].par=sam[np].par=nq;
while (p&&sam[p].ch[x]==q)
{
sam[p].ch[x]=nq;
p=sam[p].par;
}
}
}
p=np;
}

void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}

D1T3

快速幂

# 3

欧拉定理,边读入边取模。

# 4

找到最大值往上枚举 / 抱着恶臭的想法直接猜出来

# 5

按 $x$ 排序后发现有两组相邻的 $x$ 差小于等于 $10$,由于 $p|(y_119^{x_2-x_1}-y_2)$,求出这两组的 $gcd$ 即可。

# 6 / 7

先自然溢出再取模。

# 7 暴力找循环节即可。需要注意循环节中不含 $1$ .. 所以不能直接通过 $1$ 来判断循环节,可以用 set

区间筛质数/莫比乌斯函数

# 9 / 12

用 $\sqrt n$ 以内的质数筛后面的。

# 10 / 13

用 $5\times10^7$ 以内的数筛后面的,然后把错误的项打表。

好像可以用 Miller-Rabin 不打表做,不太会..

几个优化码长的小技巧:

  1. 数组里面存差分。
  2. 把 $5\times10^7$ 略微调大,但要注意不要 TLE。
  3. 把数组压成字符串。

区间筛原根

# 14

直接判断 $p-1$ 除掉每个质因数后是否是 $a^x\equiv1\pmod p$ 的解。

# 15

先找到任意一个原根 $g$。

预处理出 $x​$ 是 $g​$ 的 $k​$ 次幂,那么 $x​$ 是原根当且仅当 $k​$ 和 $p-1​$ 互质。

# 16

枚举质数判断即可快速找到 $p$。(说是快速还是要跑几十秒..)

参考代码

LOJ 最慢解

D2T1

搞三个背包:

  1. 整个城市都没有限制的城市选择阵营。
  2. 没有限制的学校选择派系。
  3. 有限制的学校选择阵营&派系,注意每个有限制的城市要选一个有限制的学校作为“代表”,在背包时对阵营的贡献为整个城市的总和。

最后再枚举第三个背包的每一项,对答案的贡献就是这一项乘上前两个背包中可以和这一项一起选的方案数,实际上是一段连续的区间,所以前两个背包预处理一下前缀和就可以算了。

用值域优化一下背包的枚举范围,总复杂度是 $\mathcal O(nm+k^2wm)$。

整体思路不难,知识点只有背包..然而还是写了整整一晚上。

在寝室调到快十二点,虽然觉得自己挺 sb 的,但本地在 lemon 上 ac 的时候..真的好爽啊。

不得不说寝室写题效率就是高,又爽。写完还能看一集三狮

参考代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=1005;
const int M=2505;
const int K=35;
const int V=10;
const int mod=998244353;

struct Node
{
int b,s,p;
bool operator<(const Node& y) const
{
if ((~p&&~y.p)||(p==-1&&y.p==-1)) return b<y.b;
if (p==-1) return false;
return true;
}
} a[N];

int n,c,m,f[M],g[M],h[M][K*V][2],zy[2],px[2],sum[N],tot[4],ans;
bool ban[N];

int main()
{
int T,i,j,k,x,y,tmp[2];

scanf("%d",&T);

while (T--)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(h,0,sizeof(h));
memset(tot,0,sizeof(tot));
memset(sum,0,sizeof(sum));
memset(ban,false,sizeof(ban));

scanf("%d%d%d%d%d%d",&n,&c,zy+0,zy+1,px+0,px+1);

for (i=1;i<=n;++i)
{
scanf("%d%d",&a[i].b,&a[i].s);
sum[a[i].b]+=a[i].s;
a[i].p=-1;
tot[0]+=a[i].s;
tot[1]+=a[i].s;
}

scanf("%d",&m);

for (i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
a[x].p=y;
ban[a[x].b]=true;
tot[0]-=a[x].s;
tot[2]+=a[x].s;
}

sort(a+1,a+n+1);

f[0]=1;
for (i=1;i<=c;++i)
{
if (ban[i]||!sum[i])
{
tot[1]-=sum[i];
tot[3]+=sum[i];
continue;
}
for (j=min(zy[0],tot[1]);j>=sum[i];--j)
{
if (j>=sum[i]) f[j]=(f[j]+f[j-sum[i]])%mod;
}
}
for (j=1;j<=zy[0];++j) f[j]=(f[j-1]+f[j])%mod;

g[0]=1;
for (i=m+1;i<=n;++i)
{
for (j=min(px[0],tot[0]);j>=a[i].s;--j)
{
if (j>=a[i].s) g[j]=(g[j]+g[j-a[i].s])%mod;
}
}
for (j=1;j<=px[0];++j) g[j]=(g[j-1]+g[j])%mod;

h[0][0][0]=1;
for (i=m;i>=1;--i)
{
for (j=min(tot[3],zy[0]);j>=0;--j)
{
for (k=tot[2];k>=0;--k)
{
for (x=0;x<=1;++x)
{
tmp[x]=0;
for (y=0;y<=1;++y)
{
if ((x^1)*2+(y^1)==a[i].p||j<x*sum[a[i].b]||k<y*a[i].s) continue;
if (a[i].b!=a[i+1].b||i==m) tmp[x]=(0ll+tmp[x]+h[j-x*sum[a[i].b]][k-y*a[i].s][x^1]+h[j-x*sum[a[i].b]][k-y*a[i].s][x])%mod;
else tmp[x]=(tmp[x]+h[j][k-y*a[i].s][x])%mod;
}
}
h[j][k][0]=tmp[0];
h[j][k][1]=tmp[1];
}
}
}

ans=0;
for (j=0;j<=tot[3]&&j<=zy[0];++j)
{
if (zy[0]-j<tot[3]-j+tot[1]-zy[1]) continue;
for (k=0;k<=tot[2];++k)
{
if (px[0]-k<tot[2]-k+tot[0]-px[1]) continue;
ans=(ans+(ll)(h[j][k][0]+h[j][k][1])*(f[zy[0]-j]-(tot[3]-j+tot[1]-zy[1]>0?f[tot[3]-j+tot[1]-zy[1]-1]:0))%mod*(g[px[0]-k]-(tot[2]-k+tot[0]-px[1]>0?g[tot[2]-k+tot[0]-px[1]-1]:0)))%mod;
}
}

cout<<(ans+mod)%mod<<endl;
}

return 0;
}

D2T2

用堆维护每个子树的答案(堆里每个元素为每一组的最大值),合并的时候弹出两个堆顶取 max 记录下来,直到其中一个堆为空,再把记录的值加到非空的那个堆里,就是新的答案。可以两两合并,也可以把儿子合并了再加上自己。合并时每弹出两个元素、加入一个元素,元素的总数就会减少一,所以总复杂度是 $\mathcal O(n\log n)$。注意,不能用 = 来复制堆,而要用 swap,而且要开 C++11。如果不开 C++11 可以记录 id 然后 swap id。

贪心合并就不严格证了,感觉稍有点类似最近那场 CF 的 B

参考代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int read()
{
int out=0;
char c;
while (!isdigit(c=getchar()));
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out;
}

const int N=200010;

void dfs1(int u);
void dfs2(int u);

vector<int> son[N];
int n,a[N],mxdep[N];
priority_queue<int> q[N];

int main()
{
int i;
long long ans=0;

n=read();

for (i=1;i<=n;++i) a[i]=read();

for (i=2;i<=n;++i) son[read()].push_back(i);

dfs1(1);

for (i=1;i<=n;++i) sort(son[i].begin(),son[i].end(),[](int x,int y){return mxdep[x]>mxdep[y];});

dfs2(1);

while (!q[1].empty())
{
ans+=q[1].top();
q[1].pop();
}

cout<<ans;

return 0;
}

void dfs2(int u)
{
int i,v,mx;
vector<int> tmp;
for (i=0;i<son[u].size();++i)
{
v=son[u][i];
dfs2(v);
}
if (son[u].size())
{
if (son[u].size()>1)
{
while (!q[son[u][1]].empty())
{
mx=0;
for (i=0;i<son[u].size();++i)
{
v=son[u][i];
if (q[v].empty()) break;
mx=max(mx,q[v].top());
q[v].pop();
}
tmp.push_back(mx);
}
}
q[u].swap(q[son[u][0]]);
for (i=0;i<tmp.size();++i) q[u].push(tmp[i]);
}
q[u].push(a[u]);
}

void dfs1(int u)
{
int i,v;
for (i=0;i<son[u].size();++i)
{
v=son[u][i];
dfs1(v);
mxdep[u]=max(mxdep[u],mxdep[v]+1);
}
}

D2T3

待填。