题解 P5290 【[十二省联考2019]春节十二响】
_虹_
2019-04-08 17:23:02
~~D2唯一看懂的题~~
~~而且考场上没看懂为啥1可能不是链端点~~
~~大力观察题意~~，这题可以贪心，直接合并子节点的priority_queue，上界n^2logn，虽然上界很松，还是怂了。
可以发现两个序列合并后，序列依然是有序的，没有必要用排序，所以可以直接用vector维护。
~~然后随机数据考场电脑随便跑~~
~~然后就没写启发式合并变成60分~~
加上启发式合并就过了QAQ。。。。
下面是比较暴力的vector做法：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define reg register
typedef long long vt;
const int kmaxn=200000+5;
struct edge
{
int d;
edge* nxt;
};
edge mempool[kmaxn];
int mpt;
edge* head[kmaxn];
void add_edge(int s,int d)
{
mempool[mpt].nxt=head[s];
head[s]=&mempool[mpt++];
head[s]->d=d;
}
vector<vt> q[kmaxn];
vt value[kmaxn];
int pos[kmaxn];
void merge(int& a,int& b)
{
if(a==0)
{
a=b;
return;
}
if(q[a].size()<q[b].size())
{
swap(a,b);
}
vt t=0;
reg int i=0,L=min(q[a].size(),q[b].size());
for(i=0;i<L;++i)
{
t=max(q[a][i],q[b][i]);
q[a][i]=t;
}
for(L=q[b].size();i<L;++i)
{
q[a].push_back(q[b][i]);
}
vector<vt> vec;
swap(vec,q[b]);
}
int lb(int num)
{
vt v=value[num];
num=pos[num];
reg int l=0,r=q[num].size();
reg int mid=0,ans=0;
if(q[num].empty()||q[num][0]<=v)
return 0;
else if(q[num].back()>v)
return r;
while(l<r)
{
mid=(l+r)>>1;
if(q[num][mid]<=v)
{
r=mid;
ans=mid;
}
else
{
l=mid+1;
}
}
return ans;
}
void dfs(int now)
{
edge* t=head[now];
while(t)
{
dfs(t->d);
merge(pos[now],pos[t->d]);
t=t->nxt;
}
if(!head[now])
{
pos[now]=now;
}
/* reg int p=pos[now];
for(reg int i=0,j=q[p].size();i<j;++i)
{
if(q[p][i]<=value[now])
{
q[p].insert(q[p].begin()+i,value[now]);
return;
}
}
q[p].push_back(value[now]);*///链会超时
q[pos[now]].insert(q[pos[now]].begin()+lb(now),value[now]);
}
int n;
int fa;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(reg int i=1;i<=n;++i){
cin>>value[i];
}
for(reg int i=2;i<=n;++i)
{
cin>>fa;
add_edge(fa,i);
}
dfs(1);
vt ans=0;
for(reg int i=q[pos[1]].size()-1;i>=0;--i)
{
ans+=q[pos[1]][i];
}
cout<<ans<<endl;
return 0;
}
```
vector做法依然可以卡，因为对序列插入每个节点权值时，上界依旧是n，不过平衡树中序遍历+启发式合并就卡不掉了
~~但是vector能过写什么平衡树~~
~~依旧偷懒，记吃不记打~~