线段树合并简单题,贪心神题!
题意简述:给定一棵树,每个点有权值\(w_i\),要求你选择一个最大的点集(不要求联通),使得若\(u是v的祖先\),则\(w_u \leq w_v\).
\(n \leq 1e5,w_i \leq 1e9\)
- 考虑设\(dp_{u,i}\)为以\(u\)为根的子树内,最大值为i能选的最大的点数,将\(w_i\)离散化.
- 有以下转移
- \(dp_{u,i} = max(max_{j = i}^{n} dp_{v,j}+ dp'_{u,i},max_{j = i}^{n} dp'_{u,j}+ dp_{v,i})\)
- \(dp_{u,{w_i}} = max(dp_{u,w_i},\sum_v max_{j = i}^{n} dp_{v,j}) + 1\)
- 如果用线段树合并你会发现这是一个弱智题.只要支持区间加,线段树合并就可以.
因为我这个弱智写了这个做法而且调了一晚上. - 时间复杂度\(O(nlogn)\),常数巨大.
- 参考了神\(dodo\)的题解题解 P4577 【[FJOI2018]领导集团问题】.有以下更加巧妙的做法.
- 考虑换一个\(dp\)状态,设\(f_{u,i}\)为以\(u\)为根的子树内,选了\(i\)个点,其最小的\(w_i\)最大可以是多少.考虑直接用\(multiset\)维护.
- 考虑如何合并.先不考虑如何加入\(w_u\)这个点,那么子树间显然互不影响,那么直接启发式合并子树即可.
- 考虑加入\(w_u\)这个点,那么我们在\(multiset\)找到\(w_u\).考虑第一个\(\leq w_u\)的点(如果存在)\(f_{u,x}\),我们直接将其删掉会更优,此时\(f_{u,x} = w_u\)且\(f_u\)集合是合法的.
- 答案即为\(|f_1|\).
- 代码是愚蠢的线段树合并.(第二种做法可以翻一下\(dodo\)大神的\(blog\))
/*[FJOI2018]领导集团问题*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool fuck = 0;
int read(){
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int N = 4e5 + 10;
struct SegmentTree{
int lc,rc;
int mx,add;
}t[N<<5];
int cnt = 0;
void pushup(int p){
t[p].mx = max(t[t[p].lc].mx,t[t[p].rc].mx);
}
void pushadd(int p,int v){
t[p].mx += v;
t[p].add += v;
}
void pushdown(int p){
if(t[p].add){
int v = t[p].add;
if(t[p].lc) pushadd(t[p].lc,v);
if(t[p].rc) pushadd(t[p].rc,v);
t[p].add = 0;
}
}
void ins(int &p,int l,int r,int pos,int v){
if(!p) p = ++cnt;
if(l == r){
t[p].mx = max(v,t[p].mx);
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if(pos <= mid) ins(t[p].lc,l,mid,pos,v);
else ins(t[p].rc,mid+1,r,pos,v);
pushup(p);
}
int query(int p,int l,int r,int a,int b){
if(!p || a > b) return 0;
if(a <= l && b >= r) return t[p].mx;
int mid = (l + r) >> 1;
pushdown(p);
int ans = 0;
if(a <= mid) ans = max(ans,query(t[p].lc,l,mid,a,b));
if(b > mid) ans = max(ans,query(t[p].rc,mid+1,r,a,b));
return ans;
}
int merge(int u,int v,int l,int r,int mx1,int mx2){
if(!u || !v){
if(!u && !v) return 0;
if(!u){
// t[v].mx = (mx1 + t[v].mx);
pushadd(v,mx1);
return v;
}
if(!v){
// t[u].mx = (mx2 + t[u].mx);
pushadd(u,mx2);
return u;
}
}
if(l == r){
mx2 = max(mx2,t[v].mx);mx1 = max(mx1,t[u].mx);
int Mx = max(t[u].mx + mx2,t[v].mx + mx1);
t[u].mx = Mx;
return u;
}
pushdown(u);pushdown(v);
int mid = (l + r) >> 1;
t[u].lc = merge(t[u].lc,t[v].lc,l,mid,max(mx1,t[t[u].rc].mx),max(mx2,t[t[v].rc].mx));
t[u].rc = merge(t[u].rc,t[v].rc,mid+1,r,mx1,mx2);
pushup(u);
return u;
}
int tmp[N],w[N],n,rt[N],k;
struct Edge{
int nxt,point;
}edge[N<<1];int head[N],tot;
void dfs(int u){
int Pyy = 1;
for(int i = head[u]; i ; i = edge[i].nxt){
int v = edge[i].point;
dfs(v);
int S1 = 0,S2 = 0;
Pyy += query(rt[v],1,k,w[u],k);
rt[u] = merge(rt[u],rt[v],1,k,S1,S2);
}
ins(rt[u],1,k,w[u],Pyy);
}
void add_edge(int u,int v){
edge[++tot].nxt = head[u];
edge[tot].point = v;
head[u] = tot;
}
int main(){
// freopen("boss10.in","r",stdin);
n = read();
for(int i = 1; i <= n; ++i) w[i] = read(),tmp[i] = w[i];
sort(tmp+1,tmp+n+1);
k = unique(tmp+1,tmp+n+1) - tmp - 1;
for(int i = 1; i <= n ; ++i) w[i] = lower_bound(tmp+1,tmp+k+1,w[i]) - tmp;
for(int i = 2; i <= n; ++i){
int fa = read();
add_edge(fa,i);
}
dfs(1);
printf("%d\n",t[rt[1]].mx);
return 0;
}