Luogu P5290 / LOJ3052 【[十二省联考2019]春节十二响】

时间:2020-12-14 04:32:10

联考Day2T2...多亏有这题...让我水了85精准翻盘进了A队...

题目大意:

挺简单的就不说了吧...(这怎么简述啊)

题目思路:

看到题的时候想了半天,不知道怎么搞。把样例画到演草纸上之后又画了几条链手动找最优解,然后发现只需要知道怎么合并子树就行了。因为题目说的很清楚,合并出来链就行,然后手动模拟了一下合并,由于有父子关系的两个点不能被合并在一起,那么从最优的角度考虑显然贪心,把其他链中的最大与当前链最大取\(\max\),第二大同理,以此类推。那么显然需要一个堆维护,然后考虑合并后的链长度,显然是以\(1\)为一个端点的最长链长。由此很容易想到树剖,先求出重链,然后把轻链合并到重链上。然而考场上蠢了,拿vector维护了链,插入数的时候插入到vector末尾然后暴力swap,结果一条链的时候T了,非常GG。

所以这题真的非常简单,就树剖之后暴力合并,实现细节详见代码qwq(所以要不是因为蠢了就直接A了)

ps:考试的时候写到namespace里面了,然后并不想再改太多,就这样写了,凑合着看一下好了qwq。(这题真的水 就连数据都是水的)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue> using namespace std; void qread(int &xx){
xx=0;int ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
while(ch>='0'&&ch<='9'){
xx=xx*10+ch-'0';
ch=getchar();
}
} const int N=2e5+5; int n,M[N],f[N],mxlen[N],lson[N]; vector<int>G[N]; namespace sub1{
void pdfs(int u){
if(!u){
return;
}
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
pdfs(v);
mxlen[u]=max(mxlen[u],mxlen[v]+1);
}
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
if(mxlen[v]==mxlen[u]-1){
lson[u]=v;
break;
}
}
mxlen[u]=max(mxlen[u],1);
}
void dfs(int u,priority_queue<int>&pq){
if(!u){
return;
}
if(lson[u]){
dfs(lson[u],pq);
}
else{
pq.push(M[u]);
return;
}
priority_queue<int>rep,repp;
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
if(v==lson[u]){
continue;
}
dfs(v,rep);
while(!rep.empty()){
repp.push(max(pq.top(),rep.top()));
pq.pop();
rep.pop();
}
while(!repp.empty()){
pq.push(repp.top());
repp.pop();
}
}
pq.push(M[u]);
}
void solve(){
long long rep=0;
priority_queue<int>ans;
pdfs(1);
dfs(1,ans);
while(!ans.empty()){
rep+=ans.top();
ans.pop();
}
printf("%lld\n",rep);
}
} void addedge(int u,int v){
G[u].push_back(v);
} int main(){
qread(n);
for(int i=1;i<=n;i++){
qread(M[i]);
}
for(int i=2;i<=n;i++){
qread(f[i]);
addedge(f[i],i);
}
sub1::solve();
return 0;
}