[FJOI2018] 领导集团问题
题目描述
一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 \(v_i\),且每个成员都有响应的级别 \(w_i\)。越高层的领导,其级别值 \(w_i\) 越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点 \(v_i\) 和 \(v_j\),如果 \(v_i\) 是 \(v_j\) 的子孙结点,则 \(w_i \ge w_j\)。
编程任务:对于任意对于给定的领导树,计算出领导树中最大的部门结点子集。
输入格式
第一行有一个正整数 \(n\),表示领导树的结点数。
接下来的一行中有 \(n\) 个整数。第 \(i\) 个数表示 \(w_i\)。
再接下来的 \(n-1\) 行中,第 \(i\) 行有一个整数 \(v_i\) 表示 \(v_i\) 是 \(i+1\) 的双亲结点。
输出格式
输出找到的最大的部门的成员数。
样例 #1
样例输入 #1
6
2 5 1 3 5 4
1
1
2
2
4
样例输出 #1
4
提示
对于 \(10\%\) 的数据,\(n\le 20\);
对于 \(40\%\) 的数据,\(n\le 2000\);
对于 \(100\%\) 的数据,\(1\le n\le 2\times 10 ^ 5\),\(0 < w_i \le 10 ^ 9\)。
/*dp式子
dp[i][j]表示在第i个点,以j为根节点的小根堆的最大个数
dp[i][v] = sigma(max(dp[son][v->n]));sigma中必须要有一个dp[son][v]
dp[i][w[i]] = max(dp[i][w[i]], sigma(max(dp[son][w[i]->n])) + 1);
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define lid (tree[id].lson)
#define rid (tree[id].rson)
const int maxN = 2e5 + 520.1314;
using namespace std;
int n, tot;
int w[maxN];
int cnt, head[maxN], nex[maxN], to[maxN];
int root[maxN], res[maxN];
struct Segment_Tree {
int lson, rson;
int dp, lazy;
}tree[maxN * 500];
struct MergeSegmentTree {
inline int NewNode() {
int id = ++ tot;
tree[id].lson = tree[id].rson = 0;
tree[id].lazy = tree[id].dp = 0;
return id;
//建立新节点
}
inline void PushDown(int id) {
if (tree[id].lazy != 0) {
int temp = tree[id].lazy;
if (lid != 0) {
tree[lid].dp = tree[lid].dp + temp;
tree[lid].lazy = tree[lid].lazy + temp;
}
if (rid != 0) {
tree[rid].dp = tree[rid].dp + temp;
tree[rid].lazy = tree[rid].lazy + temp;
}
tree[id].lazy = 0;
//若下放时没有lid或rid 那么id的lazy就不会对其造成影响
//故可以直接删除
}
return;
}
inline void PushUp(int id) {
tree[id].dp = max(tree[lid].dp, tree[rid].dp);
return;
}
void Update(int &id, int l, int r, int pos, int num) {
if (id == 0) id = NewNode();
if (l == r) {
tree[id].dp = max(tree[id].dp, num);
//找最大值
return;
}
PushDown(id);
int mid = (l + r) >> 1;
if (pos <= mid) {
Update(lid, l, mid, pos, num);
}
else {
Update(rid, mid + 1, r, pos, num);
}
PushUp(id);
return;
}
int Query(int id, int l, int r, int vl, int vr) {
int ans = 0;
if (id == 0) return 0;
if (vl <= l && r <= vr) {
return tree[id].dp;
}
PushDown(id);
int mid = (l + r) >> 1;
if (l <= mid) ans = max(ans, Query(lid, l, mid, vl, vr));
if (r > mid) ans = max(ans, Query(rid, mid + 1, r, vl, vr));
return ans;
}//单点查询
int Merge(int &a, int &b, int l, int r, int &amax, int &bmax) {
if (a == 0 && b == 0) return 0;
if (a == 0 && b != 0) {
bmax = max(bmax, tree[b].dp);
tree[b].dp += amax;
tree[b].lazy += amax;
return b;
//对应sigma(max(dp[son][v->n]))
//tree[b].dp += amax;在这里代表max(dp[b][l->r])加上max(dp[a][r->n])
//tree[b].lazy += amax;代表在l->r的区间内其他有dp值但不是max(dp[b][l->r])的地方加max(dp[a][r->n])
}
else if (a != 0 && b == 0) {
amax = max(amax, tree[a].dp);
tree[a].dp += bmax;
tree[a].lazy += bmax;
return a;
//同上
}
else if (l == r) {
amax = max(amax, tree[a].dp);
bmax = max(bmax, tree[b].dp);
tree[a].dp = max(tree[a].dp + bmax, amax + tree[b].dp);
//对应sigma中必须要有一个dp[son][v]
return a;
}
PushDown(a);
PushDown(b);//都要PushDown
int mid = (l + r) >> 1;
tree[a].rson = Merge(tree[a].rson, tree[b].rson, mid + 1, r, amax, bmax);//注意先处理后面的dp
tree[a].lson = Merge(tree[a].lson, tree[b].lson, l, mid, amax, bmax);
PushUp(a);
return a;
}
}t;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch - '0');
ch = getchar();
}
return x * f;
}
inline void AddPoi(int v1, int v2) {
++ cnt;
nex[cnt] = head[v1];
head[v1] = cnt;
to[cnt] = v2;
return;
}
void DFS(int now) {
int sum = 0;
bool flag = true;
for (int i = head[now]; i != 0; i = nex[i]) {
DFS(to[i]);
sum += t.Query(root[to[i]], 1, n, w[now], n);
}
for (int i = head[now]; i != 0; i = nex[i]) {
if (flag == true) {
root[now] = root[to[i]];//父亲节点刚开始时的线段树时是空的
flag = false;
}
else {
int lmax = 0, rmax = 0;
root[now] = t.Merge(root[now], root[to[i]], 1, n, lmax, rmax);
//将儿子的线段树合并到父亲来
}
}
t.Update(root[now], 1, n, w[now], sum + 1);
//在合并后的比较dp[i][w[i]] 与 sigma(max(dp[son][w[i]->n])) + 1的大小并更新;
return;
}
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
w[i] = read();
res[i] = w[i];
}
sort(res + 1, res + 1 + n);
int len = unique(res + 1, res + 1 + n) - (res + 1);
for (int i = 1; i <= n; ++ i) {
w[i] = lower_bound(res + 1, res + 1 + len, w[i]) - res;
}//离散化
for (int i = 1, temp; i <= n - 1; ++ i) {
temp = read();
AddPoi(temp, i + 1);
}
DFS(1);
printf("%d\n", t.Query(root[1], 1, n, 1, n));
//输出答案
return 0;
}
标签:lazy,P4577,int,Luogu,tree,FJOI2018,max,id,dp
From: https://www.cnblogs.com/jueqingfeng/p/17468807.html