题解 P5290 【[十二省联考2019]春节十二响】
龙之吻—水货
2019-04-10 13:35:32
# [十二省联考2019]春节十二响
## 题目大意
给定一棵树，每次选取树上的一个点集，要求点集中的每个点不能是另一个点的祖先，选出点集的代价为点集中权值最大点的权值，问将所有点都选一遍的最小代价为多少。
## 解题报告
似乎其他题解都是将整棵树最后合并成为一个链统计答案的，不过在考场上我并没有到这种方法，而是使用了一种贪心的方法。
尽管到现在我都无法证明它的正确性，但是在它的确可以通过所有的测试点，在考场上也帮我得到了 $100$ 分的，那么就暂且相信它是正确的吧 QwQ
首先，我们将所有点按从大到小的顺序进行排序，然后我们枚举每一个点，如果当前点被选过了的话就跳过。之后，我们将这点点放入一个新的点集中。然后，我们从大到小枚举这个点之后的点，能加则加，不能加就跳过，放一个伪代码就是 :
```
sort i in val
for i 1 to n :
if i is used :
continue
make a new set
put i into the set
for j i + 1 to n :
if j is used :
continue
if j can't be put into set :
continue
put j into set
j is used
```
那么我们现在所需要的就是判断一个点能否被放在点集中，以及找出可选点中最大的点。
显然，我们每选择一个点之后，这个点到根的路径上所有的点，以及这个点为根的子树里面所有的点都不能被选择了。
我们发现，我们现在需要一个支持在树上修改子树，修改链，查询全树最大值的数据结构，而树链剖分可以完美地解决这个问题。
具体来说就是，在线段树上的每个节点维护这段区间是否可选，以及这段区间的最大值。每向集合中加入一个点之后，先将这个点的删除，然后将这个点到根的路径上，以及这个点为根的子树打上一个不可选标记，之后每次从线段树中取出那个最大值即可。当我们选完一个集合之后，要注意把之前的不可选标记清除掉，具体实现可以看代码。
由于每个点只会被处理一次，所以总的时间复杂度为 $O(n\log^2n)$ ，虽然看起来 $2 \times 10^5$ 有点悬，但事实证明出题人并没有特意去卡这个算法，所以就可以 $AC$ 啦！
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
class SegmentTree{
private :
static const int maxn = 2e5 + 7;
struct Node{
int max, del;
Node *child[2];
Node() : max(0), del(0) {
child[0] = child[1] = NULL;
}
};
int n, *val;
Node *root, pool[maxn << 2], *tp;
Node *newNode() {
*++tp = Node();
return tp;
}
void update(Node *now) {
now->max = 0;
for (register int i = 0; i < 2; i++) {
if (now->child[i]->del) {
continue;
}
if (val[now->child[i]->max] > val[now->max]) {
now->max = now->child[i]->max;
}
}
}
void buildTree(Node *now, int left, int right) {
if (left == right) {
now->max = left;
return;
}
int mid = (left + right) >> 1;
buildTree(now->child[0] = newNode(), left, mid);
buildTree(now->child[1] = newNode(), mid + 1, right);
update(now);
}
void delMax(Node *now, int left, int right, int l, int r) {
if (left >= l && right <= r) {
now->del = 1;
return;
}
int mid = (left + right) >> 1;
if (r <= mid) {
delMax(now->child[0], left, mid, l, r);
} else if (l > mid) {
delMax(now->child[1], mid + 1, right, l, r);
} else {
delMax(now->child[0], left, mid, l, r);
delMax(now->child[1], mid + 1, right, l, r);
}
update(now);
}
void addMax(Node *now, int left, int right, int l, int r) {
if (left >= l && right <= r) {
now->del = 0;
return;
}
int mid = (left + right) >> 1;
if (r <= mid) {
addMax(now->child[0], left, mid, l, r);
} else if (l > mid) {
addMax(now->child[1], mid + 1, right, l, r);
} else {
addMax(now->child[0], left, mid, l, r);
addMax(now->child[1], mid + 1, right, l, r);
}
update(now);
}
void eraseMax(Node *now, int left, int right, int pos) {
if (left == right) {
now->max = 0;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid) {
eraseMax(now->child[0], left, mid, pos);
} else {
eraseMax(now->child[1], mid + 1, right, pos);
}
update(now);
}
public :
void init(int x, int *m) {
n = x, val = m, tp = pool;
buildTree(root = newNode(), 1, n);
}
void delMax(int l, int r) {
//printf("del : %d %d\n", l, r);
delMax(root, 1, n, l, r);
}
void addMax(int l, int r) {
//printf("add : %d %d\n", l, r);
addMax(root, 1, n, l, r);
}
void eraseMax(int pos) {
eraseMax(root, 1, n, pos);
}
int queryMax() {
//printf("%d %d\n", root->del, root->max);
return root->del ? 0 : root->max;
}
};
const int maxn = 2e5 + 7;
int m[maxn];
class Solution{
private :
typedef long long ll;
typedef std::pair<int, int> par;
int n, id[maxn], fa[maxn], size[maxn], son[maxn], top[maxn];
int h[maxn], cnt, dfn[maxn], red[maxn], end[maxn], val[maxn];
ll ans;
bool used[maxn], have[maxn];
std::vector<int> e[maxn];
std::queue<int> q;
SegmentTree tree;
static bool cmp(int a, int b) {
return m[a] > m[b];
}
void DFS1(int now) {
h[now] = h[fa[now]] + 1;
size[now] = 1;
for (auto v : e[now]) {
DFS1(v);
size[now] += size[v];
if (size[v] > size[son[now]]) {
son[now] = v;
}
}
}
void DFS2(int now, int tp) {
red[end[now] = dfn[now] = ++cnt] = now;
val[cnt] = m[now];
top[now] = tp;
if (son[now]) {
DFS2(son[now], tp);
end[now] = end[son[now]];
}
for (auto v : e[now]) {
if (v == son[now]) {
continue;
}
DFS2(v, v);
end[now] = end[v];
}
//printf("%d : %d %d\n", now, dfn[now], end[now]);
}
inline void mark(int now) {
q.push(now);
tree.eraseMax(dfn[now]);
for (register int i = now; i && !have[i]; i = fa[top[i]]) {
tree.delMax(dfn[top[i]], dfn[i]);
}
tree.delMax(dfn[now], end[now]);
//DFS(now);
}
inline void delMark(int now) {
for (register int i = now; i && !have[i]; i = fa[top[i]]) {
tree.addMax(dfn[top[i]], dfn[i]);
}
tree.addMax(dfn[now], end[now]);
}
void DFS(int now) {
have[now] = 1;
for (auto v : e[now]) {
DFS(v);
}
}
public :
Solution() {
get();
solve();
}
void get() {
scanf("%d", &n);
for (register int i = 1; i <= n; i++) {
scanf("%d", m + i);
id[i] = i;
//pq.push(std::make_pair(m[i], i));
}
for (register int i = 2; i <= n; i++) {
scanf("%d", fa + i);
e[fa[i]].push_back(i);
}
}
void solve() {
DFS1(1);
DFS2(1, 1);
//printf("%d\n", dfn[11]);
tree.init(n, val);
//printf("%d %d\n", dfn[1], end[1]);
for (register int now = tree.queryMax(); now; now = tree.queryMax()) {
now = red[now];
//printf("%d : ", now);
ans += m[now];
mark(now);
for (register int p = tree.queryMax(); p; p = tree.queryMax()) {
p = red[p];
//printf("%d ", p);
mark(p);
}
while (!q.empty()) {
delMark(q.front());
q.pop();
}
//putchar('\n');
}
printf("%lld\n", ans);
}
};
Solution sol;
int main() {}
```