2019各省省选试题选做
2019各省省选试题选做
施工中
目前已更新：
- [ ] ZJOIDay1T1 麻将
- [x] ZJOIDay1T2 线段树
- [x] ZJOIDay1T3 Minimax搜索
- [x] HNOIDay1T1 鱼
- [x] HNOIDay1T2 JOJO
- [x] HNOIDay1T3 多边形
- [x] HNOIDay2T1 校园旅行
- [x] HNOIDay2T2 白兔之舞
- [x] HNOIDay2T3 序列
- [x] 十二省联考Day1T1 异或粽子
- [x] 十二省联考Day1T2 字符串问题
- [ ] 十二省联考Day1T3 骗分过样例
- [x] 十二省联考Day2T1 皮配
- [x] 十二省联考Day2T2 春节十二响
- [ ] 十二省联考Day2T3 希望
ZJOI
Day1T2 线段树
可以发现操作的意义等价于，每次以\(\frac 12\)的概率进行一次区间覆盖操作，求线段树上有标记节点的期望个数。根据期望的线性性，只需要求出每个节点有标记的概率\(f_i\)再求和即可。
为了方便的维护这个概率，我们需要额外对线段树上每个点维护该点到根的路径上有标记的概率\(g_i\)。每次修改都会有\(O(\log n)\)个节点的\(f_i\)值变成\(\frac{f_i}{2}\)或\(\frac{f_i+1}{2}\)或\(\frac{f_i+g_i}{2}\)中的一种（请根据实际含义自行理解），而同时也会有\(O(\log n)\)棵线段树子树内的\(g_i\)值变成\(\frac{g_i+1}{2}\)。
在具体实现中，可以维护\(g_i'=1-g_i\)，这样对子树内\(g_i'\)的修改就变成了\(g_i'\gets \frac{g_i'}{2}\)，直接打区间乘法标记（或者直接记区间要除几次\(2\)）即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=4e5+5;
const int mod=998244353;
int n,m,pw,inv[N],f[N],g[N],tag[N],ans;
void build(int x,int l,int r){
g[x]=1;if(l==r)return;int mid=l+r>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void upt(int x,int v){ans=(ans-f[x]+mod)%mod;f[x]=1ll*(f[x]+v)*inv[1]%mod;ans=(ans+f[x])%mod;}
void cover(int x,int v){g[x]=1ll*g[x]*inv[v]%mod;tag[x]+=v;}
void down(int x){if(tag[x])cover(x<<1,tag[x]),cover(x<<1|1,tag[x]);tag[x]=0;}
void modify(int x,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){upt(x,1);cover(x,1);return;}
down(x);int mid=l+r>>1;
if(ql<=mid)modify(x<<1,l,mid,ql,qr);
else upt(x<<1,mod+1-g[x<<1]);
if(qr>mid)modify(x<<1|1,mid+1,r,ql,qr);
else upt(x<<1|1,mod+1-g[x<<1|1]);
upt(x,0);g[x]=1ll*(g[x]+1)*inv[1]%mod;
}
int main(){
n=gi();m=gi();pw=1;build(1,1,n);
inv[0]=1;inv[1]=mod+1>>1;
for(int i=2;i<=m;++i)inv[i]=1ll*inv[i-1]*inv[1]%mod;
for(int i=1,l,r;i<=m;++i)
if(gi()&1)l=gi(),r=gi(),pw=(pw<<1)%mod,modify(1,1,n,l,r);
else printf("%lld\n",1ll*ans*pw%mod);
return 0;
}Day1T3 Minimax搜索
考虑对每个\(R\)求出\(ans_R\)表示有多少个叶子集合满足权值\(\le R\)，差分即可得到答案。设树上共有\(k\)个叶子节点，易知\(ans_n=2^k-1\)。
由于我们只需要改变\(w\)的值，而变成的值的可行域显然是连续的，所以我们只需要尝试着将这个值改为\(w+1\)或\(w-1\)即可。
如果可修改集合包含\(w\)那么其权值一定为\(1\)（只要把\(w\)改掉就万事大吉了），因此\(ans_1=2^{k-1}\)。
否则，如果想要把权值变成\(w+1\)，那么大于\(w\)的点的权值显然不会被修改，而小于\(w\)的点的权值会被尽量改成\(w+1\)（如果修改代价不超过\(R\)的话）。把权值变成\(w-1\)的过程同理。可以发现两类修改互不影响，所以我们只要分别求出两类操作下\(w\)没有被改变的方案数，直接相乘得到的就是\(w\)没有被改变的方案数。
设\(f_i\)表示\(i\)点权值\(\le w\)的概率（设概率而非方案数可以方便转移），这样奇数深度的转移为\(f_u=\prod f_v\)，偶数层的转移为\(f_u=1-\prod(1-f_v)\)。同理，设\(g_i\)表示\(i\)点权值\(< w\)的概率，转移与\(f\)的转移完全一致。注意在这里\(f_i\)只考虑所有\(<w\)的叶子，\(g_i\)只考虑所有\(>w\)的叶子。
由此在\(R\)确定的情况下我们可以通过一遍树形\(dp\)求出\(ans_R=2^{k-1}(1-f_1(1-g_1))+2^{k-1}\)。这样我们就得到了一个\(O(n(R-L+1))\)的做法，可以获得\(70\)分。
满分做法其实很显然。\(R\)从\(2\)向\(n-1\)移动时每次只会改变至多两个叶子的\(dp\)值，因此使用动态\(dp\)实现即可，复杂度\(O(n\log^2n)\)，可以获得\(100\)分。
在具体实现中，由于深度奇偶性不同导致转移不同，故可以令\(f_i'=[\mbox{i点深度为奇数}]f_i+[\mbox{i点深度为偶数}](1-f_i)\)，这样转移就可以统一为\(f_u'=\prod(1-f_v')\)。
此外在动态\(dp\)的过程中可能会出现乘\(0\)后除\(0\)的问题，需要开一个\(pair\)记录\(dp\)值非零部分的乘积以及乘\(0\)的个数，从而实现信息可减。
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=2e5+5;
const int M=8e5+5;
const int mod=998244353;
int n,ans_ql,ans_qr,w,pw=1,mrk[N],fa[N],dep[N],sz[N],son[N],top[N],bot[N],dfn[N],id[N],tim,dp[2][N],ans[N];
int ls[M],rs[M],sum[2][M],prd[2][M],rt[N],tot;
vector<int>E[N];
void upt(int &x,int y,int z){z?x=max(x,y):x=min(x,y);}
int dfs(int u,int f,int d){
if(f&&E[u].size()==1){mrk[u]=1;pw=(pw<<1)%mod;return u;}
int res=d&1?0:1<<30;
for(int v:E[u])if(v!=f)upt(res,dfs(v,u,d+1),d&1);
return res;
}
int fastpow(int a,int b){
int res=1;
while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
return res;
}
struct num{
int x,y;
num(){x=1,y=0;}
num(int _x,int _y){x=_x,y=_y;}
int val(){return y?0:x;}
void mul(num b){x=1ll*x*b.x%mod,y+=b.y;}
void div(num b){x=1ll*x*fastpow(b.x,mod-2)%mod,y-=b.y;}
}g[2][N];
num Init(int x){x>=mod?x-=mod:x;return x?num(x,0):num(1,1);}
void dfs1(int u,int f){
fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
for(int v:E[u])if(v!=f){
dfs1(v,u);sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
if(son[u]){
dp[0][u]=dp[1][u]=1;
for(int v:E[u])if(v!=f){
dp[0][u]=1ll*dp[0][u]*(mod+1-dp[0][v])%mod;
dp[1][u]=1ll*dp[1][u]*(mod+1-dp[1][v])%mod;
}
}else dp[0][u]=(u>w)^(dep[u]&1),dp[1][u]=(u>=w)^(dep[u]&1);
}
void dfs2(int u,int f){
top[u]=f;id[dfn[u]=++tim]=u;
if(son[u]){
dfs2(son[u],f);
for(int v:E[u])
if(v!=fa[u]&&v!=son[u])
dfs2(v,v),g[0][u].mul(Init(mod+1-dp[0][v])),g[1][u].mul(Init(mod+1-dp[1][v]));
}else{
g[0][u]=Init(dp[0][u]);g[1][u]=Init(dp[1][u]);
for(int v=u;top[v]==top[u];v=fa[v])bot[v]=u;
}
}
void up(int x,int len){
sum[0][x]=(sum[0][ls[x]]+1ll*(len&1?mod-prd[0][ls[x]]:prd[0][ls[x]])*sum[0][rs[x]])%mod;
prd[0][x]=1ll*prd[0][ls[x]]*prd[0][rs[x]]%mod;
sum[1][x]=(sum[1][ls[x]]+1ll*(len&1?mod-prd[1][ls[x]]:prd[1][ls[x]])*sum[1][rs[x]])%mod;
prd[1][x]=1ll*prd[1][ls[x]]*prd[1][rs[x]]%mod;
}
void build(int &x,int l,int r){
x=++tot;
if(l==r){
sum[0][x]=prd[0][x]=g[0][id[l]].val();
sum[1][x]=prd[1][x]=g[1][id[l]].val();
return;
}
int mid=l+r>>1;
build(ls[x],l,mid);build(rs[x],mid+1,r);
up(x,mid-l+1);
}
void modify(int x,int l,int r,int p){
if(l==r){
sum[0][x]=prd[0][x]=g[0][id[l]].val();
sum[1][x]=prd[1][x]=g[1][id[l]].val();
return;
}
int mid=l+r>>1;
p<=mid?modify(ls[x],l,mid,p):modify(rs[x],mid+1,r,p);
up(x,mid-l+1);
}
void work(int u,int x){
int v=top[u];
if(fa[v])g[x][fa[v]].div(Init(mod+1-sum[x][rt[v]]));
modify(rt[v],dfn[top[v]],dfn[bot[v]],dfn[u]);
if(fa[v])g[x][fa[v]].mul(Init(mod+1-sum[x][rt[v]])),work(fa[v],x);
}
int main(){
n=gi();ans_ql=gi();ans_qr=gi();
for(int i=1;i<n;++i){
int x=gi(),y=gi();
E[x].push_back(y);E[y].push_back(x);
}
w=dfs(1,0,1);dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;++i)if(i==top[i])build(rt[i],dfn[top[i]],dfn[bot[i]]);
ans[1]=pw=1ll*pw*(mod+1>>1)%mod;
for(int i=2;i<n;++i){
if(w+1-i>=1&&mrk[w+1-i])g[0][w+1-i]=Init(mod+1>>1),work(w+1-i,0);
if(w+i-1<=n&&mrk[w+i-1])g[1][w+i-1]=Init(mod+1>>1),work(w+i-1,1);
ans[i]=(1ll*(mod-sum[0][rt[1]])*(mod+1-sum[1][rt[1]])+2)%mod*pw%mod;
}
ans[n]=(pw+pw-1)%mod;
for(int i=ans_ql;i<=ans_qr;++i)printf("%d ",(ans[i]-ans[i-1]+mod)%mod);
puts("");return 0;
}HNOI
十二省联考
Day1T1 异或粽子
把所有右端点丢到堆里，每次取出最大的即可，需要实现可持久化\(Trie\)树上求异或第\(k\)大。复杂度\(O(n\log a_i+k\log n+k\log a_i)\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define ui unsigned int
const int N=5e5+5;
struct node{int ch[2],sz;}t[N*35];
int n,k,rt[N],tot;ui a[N];
priority_queue<pair<ui,pair<int,int> > >Q;
unsigned long long ans;
void modify(int &x,ui p,int d){
t[++tot]=t[x];++t[x=tot].sz;if(d==-1)return;
modify(t[x].ch[p>>d&1],p,d-1);
}
ui query(int x,ui p,int d,int k){
if(d==-1)return 0;int c=(p>>d&1)^1;
if(k<=t[t[x].ch[c]].sz)return query(t[x].ch[c],p,d-1,k)|1u<<d;
else return query(t[x].ch[c^1],p,d-1,k-t[t[x].ch[c]].sz);
}
int main(){
scanf("%d%d",&n,&k);modify(rt[0],0,31);
for(int i=1;i<=n;++i){
scanf("%u",&a[i]);a[i]^=a[i-1];
modify(rt[i]=rt[i-1],a[i],31);
}
for(int i=1;i<=n;++i){
ui val=query(rt[i-1],a[i],31,1);
Q.push(make_pair(val,make_pair(i,1)));
}
while(k--){
ans+=Q.top().first;
int x=Q.top().second.first,y=Q.top().second.second;Q.pop();
if(y<x){
ui val=query(rt[x-1],a[x],31,++y);
Q.push(make_pair(val,make_pair(x,y)));
}
}
printf("%llu\n",ans);return 0;
}Day1T2 字符串问题
\(A_x\)向所有它支配的\(B_y\)连边，而\(B_i\)向所有以它为前缀的\(A_j\)连边。上述方式建图后，最终答案记为图中以\(A\)串长度为权值的最长路。
直接暴力建边的边数是\(O(n^2)\)级别的，显然难以承受。考虑优化这个建边过程。
建\(SAM\)后从上往下连边就行啦，注意同一个节点内的所有串要按照长度排序（长度相同时\(B\)串要排在\(A\)串的前面）后串成一条链。这样建图的总点数不超过\(2n_a+n_b+SAM\)节点数。
此外：
数据千万条，清空第一条。
多测不清空，爆零两行泪。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=4e5+5;
const int M=2e6+5;
struct node{
int x,y;
bool operator < (const node &b)const
{return x==b.x?y>b.y:x<b.x;}
};
int n,na,nb,m,tot,lst,tr[N][26],fa[N][20],len[N],pos[N],cnt,val[M],in[M],q[M],hd,tl;
long long dp[M],ans;char s[N];vector<int>T[N],E[M];vector<node>vec[N];
void extend(int c){
int v=lst,u=++tot;len[u]=len[v]+1;lst=u;
while(v&&!tr[v][c])tr[v][c]=u,v=fa[v][0];
if(!v)fa[u][0]=1;
else{
int x=tr[v][c];
if(len[x]==len[v]+1)fa[u][0]=x;
else{
int y=++tot;
memcpy(tr[y],tr[x],sizeof(int)*26);
fa[y][0]=fa[x][0];fa[x][0]=fa[u][0]=y;len[y]=len[v]+1;
while(v&&tr[v][c]==x)tr[v][c]=y,v=fa[v][0];
}
}
}
void dfs1(int u){
for(int i=1;i<20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:T[u])dfs1(v);
}
int getpos(int l,int r){
int u=pos[r];
for(int i=19;~i;--i)if(len[fa[u][i]]>=r-l+1)u=fa[u][i];
return u;
}
void link(int x,int y){E[x].push_back(y),++in[y];}
void dfs2(int u){
if(vec[u].empty())vec[u].push_back((node){0,++cnt});
sort(vec[u].begin(),vec[u].end());
for(int i=0,sz=vec[u].size();i<sz-1;++i)link(vec[u][i].y,vec[u][i+1].y);
if(u>1)link(vec[fa[u][0]].back().y,vec[u].front().y);
for(int v:T[u])dfs2(v);
}
int main(){
int Case=gi();while(Case--){
for(int i=1;i<=tot;++i){
len[i]=pos[i]=0;T[i].clear();vec[i].clear();
memset(tr[i],0,sizeof(int)*26);
memset(fa[i],0,sizeof(int)*20);
}
for(int i=1;i<=cnt;++i)in[i]=val[i]=dp[i]=0,E[i].clear();
tot=lst=1;cnt=hd=tl=ans=0;
scanf("%s",s+1);n=strlen(s+1);reverse(s+1,s+n+1);
for(int i=1;i<=n;++i)extend(s[i]-'a'),pos[i]=lst;
for(int i=2;i<=tot;++i)T[fa[i][0]].push_back(i);dfs1(1);
na=gi();for(int i=1;i<=na;++i){
int r=n-gi()+1,l=n-gi()+1,x=getpos(l,r);val[i]=r-l+1;
link(i+na,i);vec[x].push_back((node){r-l+1,i+na});
}
nb=gi();for(int i=1;i<=nb;++i){
int r=n-gi()+1,l=n-gi()+1,x=getpos(l,r);
vec[x].push_back((node){r-l+1,i+na+na});
}
cnt=na+na+nb;dfs2(1);
m=gi();for(int i=1,x,y;i<=m;++i)x=gi(),y=gi(),link(x,y+na+na);
for(int i=1;i<=cnt;++i)if(!in[i])dp[i]=val[i],q[++tl]=i;
while(hd<tl){
int u=q[++hd];ans=max(ans,dp[u]);
for(int v:E[u]){
dp[v]=max(dp[v],dp[u]+val[v]);
if(!--in[v])q[++tl]=v;
}
}
printf("%lld\n",tl<cnt?-1:ans);
}
return 0;
}Day2T1 皮配
在没有任何城市限制与偏好限制的情况下，对一个人数为\(s\)的学校定义其二元生成函数\(1+x^s+y^s+x^sy^s\)。将所有学校的生成函数\(\prod\)起来，由于总人数已知，所以\(C_0,C_1,D_0,D_1\)等价于对\(x\)与\(y\)的指数做了一定的范围限制（在某个\([l,r]\)之间）。
对于一座没有任何偏好的城市，设其学校人数集合为\(S\)，则其生成函数为\((1+y^{sum(S)})\prod_{s\in S}(1+x^s)=\prod_{s\in S}(1+x^s)+y^{sum(S)}\prod_{s\in S}(1+x^s)\)。若存在一些学校存在偏好，则该学校对应在\(1\)或\(y^{sum(S)}\)中的\(1\)或\(x^s\)项要被删去，而这并不会影响到其余没有偏好的学校（因为对于其余的学校你仍可以提一个\((1+x^s)\)项出去），而所有无关的项中\(x\)和\(y\)相对独立，所以可以先分别\(O(nm)\)地计算没有偏好的学校及城市的生成函数，再\(O(km^2)\)地暴力\(dp\)存在偏好的学校的生成函数。由于限制了单所学校的人数上限，所以实际上复杂度只有\(O(k^2ms_i)\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=2505;
const int mod=998244353;
int n,c,C0,C1,D0,D1,m,S,b[N],s[N],h[N],sum[N],mrk[N],f[N],g[N],dp[N][N],tmp[N][N];
inline void Inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
int cal(int x,int y){
int i=max(S-D1-y,0),j=D0-y,l=max(S-C1-x,0),r=C0-x;
if(i>j||l>r)return 0;return 1ll*(f[j]-f[i-1]+mod)*(g[r]-g[l-1]+mod)%mod;
}
int main(){
int Case=gi();while(Case--){
n=gi();c=gi();C0=gi();C1=gi();D0=gi();D1=gi();m=max(max(C0,C1),max(D0,D1));S=0;
memset(sum,0,sizeof(sum));memset(mrk,0,sizeof(mrk));
for(int i=1;i<=n;++i)b[i]=gi(),s[i]=gi(),sum[b[i]]+=s[i],S+=s[i],h[i]=-1;
for(int i=1,x,k=gi();i<=k;++i)x=gi(),h[x]=gi(),mrk[b[x]]=1;
memset(f,0,sizeof(f));f[0]=1;
for(int i=1;i<=n;++i)if(h[i]==-1)for(int j=m;j>=s[i];--j)Inc(f[j],f[j-s[i]]);
for(int i=1;i<=m;++i)Inc(f[i],f[i-1]);
memset(g,0,sizeof(g));g[0]=1;
for(int i=1;i<=c;++i)if(sum[i]&&!mrk[i])for(int j=m;j>=sum[i];--j)Inc(g[j],g[j-sum[i]]);
for(int i=1;i<=m;++i)Inc(g[i],g[i-1]);
memset(dp,0,sizeof(dp));memset(tmp,0,sizeof(tmp));
dp[0][0]=1;int nx=0,ny=0;
for(int i=1;i<=c;++i)
if(mrk[i]){
for(int x=0;x<=nx;++x)
for(int y=0;y<=ny;++y)
tmp[x][y]=dp[x][y];
for(int j=1;j<=n;++j)
if(b[j]==i&&h[j]!=-1){
ny=min(ny+s[j],m);
if(h[j]==1)
for(int x=0;x<=nx;++x){
for(int y=ny;y>=s[j];--y)dp[x][y]=dp[x][y-s[j]];
for(int y=0;y<s[j];++y)dp[x][y]=0;
}
if(h[j]>=2)
for(int x=0;x<=nx;++x)
for(int y=ny;y>=s[j];--y)
Inc(dp[x][y],dp[x][y-s[j]]);
if(h[j]==3)
for(int x=0;x<=nx;++x){
for(int y=ny;y>=s[j];--y)tmp[x][y]=tmp[x][y-s[j]];
for(int y=0;y<s[j];++y)tmp[x][y]=0;
}
if(h[j]<=1)
for(int x=0;x<=nx;++x)
for(int y=ny;y>=s[j];--y)
Inc(tmp[x][y],tmp[x][y-s[j]]);
}
nx=min(nx+sum[i],m);
for(int x=nx;~x;--x)
for(int y=0;y<=ny;++y)
dp[x][y]=(x>=sum[i]?dp[x-sum[i]][y]:0),Inc(dp[x][y],tmp[x][y]);
}
int ans=0;
for(int x=0;x<=nx;++x)
for(int y=0;y<=ny;++y)
Inc(ans,1ll*dp[x][y]*cal(x,y)%mod);
printf("%d\n",ans);
}
return 0;
}Day2T2 春节十二响
根节点显然自成一组，所以只需要考虑合并根的若干子树。显然最优策略会是：两棵子树内最大值分在一组，次大值分在一组......可以通过数学归纳证明一定不存在更优操作。
由于需要支持动态插入（根节点），因此考虑使用堆来维护子树内的决策。使用长链剖分，每次计算时先\(O(1)\)继承长儿子，再暴力地合并其余儿子，复杂度可以做到\(O(n\log n)\)。
使用priority_queue::swap可以做到\(O(1)\)交换两个堆（不同于std::swap的复杂度是\(O(size)\)的）。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=2e5+5;
int n,val[N],len[N],son[N];
priority_queue<int>Q[N];vector<int>E[N],tmp;
void dfs1(int u){
for(int v:E[u])dfs1(v),son[u]=len[v]>len[son[u]]?v:son[u];
len[u]=len[son[u]]+1;
}
void dfs2(int u){
for(int v:E[u])dfs2(v);
if(son[u]){
Q[u].swap(Q[son[u]]);
for(int v:E[u])if(v!=son[u]){
while(!Q[v].empty())tmp.push_back(max(Q[u].top(),Q[v].top())),Q[u].pop(),Q[v].pop();
while(!tmp.empty())Q[u].push(tmp.back()),tmp.pop_back();
}
}
Q[u].push(val[u]);
}
int main(){
n=gi();
for(int i=1;i<=n;++i)val[i]=gi();
for(int i=2;i<=n;++i)E[gi()].push_back(i);
dfs1(1);dfs2(1);long long ans=0;
while(!Q[1].empty())ans+=Q[1].top(),Q[1].pop();
printf("%lld\n",ans);return 0;
}
更多精彩
