[BZOJ4632]树的编码

试题描述

SHUXK 正在对一棵N个结点的有根树进行研究，首要的一件事就是对这棵树进行编码。

lz 说：“这还不容易吗？我令根节点的编号为 1，然后保证每个结点的编号都比它的父亲结点的编号大。这样不

就行了吗？”但 SHUXK 对这种编码方案并不满意，因为没什么特色，从中也得不到什么有用的信息。于是他想出

了一种新的编码，这种编码需要满足两个条件：

1. 作为一个 OIer，应该保证每个结点的编码是一个 01 串；

2. 为了体现树的特点，假设??号结点的编码为Si，应该有如下性质：

如果结点U是结点V的祖先，那么Su就应该是Sv的前缀；

如果结点U不是结点V的祖先或后代，那么Su就不允许是Sv的前缀。

lz 说：“ 这样编码确实有特色。但是这样一来，编码会很长呀！”

SHUXK 说：“我们就来求一种最优的编码，使得所有结点的编码长度之和最小。”当然， lz 和 SHUXK 都已经从

OI 界退役了，他们讨论完了以后就把这个任务交给你了。

输入

输入文件的第一行包含一个正整数N(N<=10^5)，表示棋盘的大小。

第二行包含N - 1个整数，分别表示2~N号结点的父亲结点Fi（保证Fi<i，也就是说 lz 已经编码好了）。

输出

输出文件只有一行一个整数，表示所有结点编码长度之和的最小值。

输入示例

输出示例

数据规模及约定

见“输入”

题解

考虑菊花图，即只有 2 层的情况，那么就是贪心地合并，每次合并的代价为两个集合大小总和，合并之后删掉原来两个集合，添加一个新集合，其大小等于两集合大小总和。仔细想想便知，这里所花的“代价”即为所用编码的长度。那么策略是每次找到两个最小的集合合并，用堆维护即可。

现在问题是对于一个节点，它有许多孩子，每个儿子节点 i 有一个子树大小 siz[i]。不难发现我们可以继续上面的合并，即从下而上按照上面的策略合并。一个子树内所对应的所有集合合并后大小即为该子树大小。所以以子树大小为关键字每次找到两个最小的集合合并，累计答案。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 100010

#define maxm 200010

int n, m, fa[maxn], head[maxn], next[maxm], to[maxm];

void AddEdge(int a, int b) {

	to[++m] = b; next[m] = head[a]; head[a] = m;

	swap(a, b);

	to[++m] = b; next[m] = head[a]; head[a] = m;

	return ;

}

priority_queue <int> Q;

int siz[maxn], ans;

void build(int u) {

	siz[u] = 1;

	for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u]) {

		build(to[e]);

		siz[u] += siz[to[e]];

	}

	for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u]) Q.push(-siz[to[e]]);

	while(!Q.empty()) {

		int u1 = -Q.top(), u2; Q.pop();

		if(Q.empty()) break;

		u2 = -Q.top(); Q.pop();

		Q.push(-u1 - u2);

		ans += u1 + u2;

	}

	return ;

}

int main() {

	n = read();

	for(int i = 2; i <= n; i++) AddEdge(i, fa[i] = read());

	build(1);

	printf("%d\n", ans);

	return 0;

}

秒客网

[BZOJ4632]树的编码

相关文章