P3565 [POI2014] HOT-Hotels - 题解
落木之樱meow
·
·
题解
P3565 [POI2014] HOT-Hotels - 题解
0-前言
看题解区发现感觉我这个思路很独特，没有做法相同的题解，因此写一篇希望能加入题解区。
优点：思路非常简单、代码短（正常精简完约50行）、比较暴力不用推复杂的dp式。
缺点：只有 O(n^2) 复杂度，没有想到优化做法。
1-分析
观察：数据范围 n\leq5000 ，发现这个题可以 O(n^2) 过，而由于很多较为简单树形dp是可以 O(n) 做的，因此外层 O(n) 枚举所有点，内层 O(n) 来统计答案。
这里枚举的 root 为定好三个选点中的一个选点，统计所有方案。由于方案会重复，总数除以 3! = 6 。
在下面分析中， root 设为 1 ，并且 lca 为三个点的“中转站”。
先看最简单的一个例子：
将 3 作为 lca ，则 1, 2, 4 可以凑成一种方案。将这个图放大：
我们现在已经选定 1 为必选，发现 lca 为 3 ，方案为 1, 5, 7 。
方便考虑，我们设根节点深度 dep[root]=0 ，两点距离为 d 。
我们观察不难得到除了 root 以外两个点 a, b 必须满足：
dep_a = dep_b = (dep_a + dep_b - 2dep_{lca}) = d
推导得 dep_{lca} = \frac{d}{2} 。
因此我们在每个 lca 上记录子树中 d_i = d_{lca} 的数量，然后算配对数量即可。
考虑以下情况：
观察不难得到：6, 7 无法和 1 配对成为一种方案。
这启示我们待选点 lca(a, b) 必须是我们确定的 lca 。（解释：7, 8 的最近公共祖先为 6 而不是 3，因此无法相互配对对根节点产生贡献。）
因此我们分不同子树考虑：若设每棵子树对 lca 贡献为 c_i ，所有子树总贡献为 sum ，则 root 这轮 lca 对答案的贡献为：
$c_i$ 对父亲以上节点没有影响，因此可以开一个树高大小的数组记录。
最后答案除以 $3! = 6$ 。
### 2-实现
枚举所有点，先求一遍所有能当 $lca$ 点的贡献，然后单个子树计算。最后答案不要忘记去重。
```c++
#include <stdio.h>
#include <vector>
#define N 5010
#define ll long long
struct edge{
int next, to;
edge() {}
edge(int NXT, int T) {next = NXT, to = T;}
} e[N * 2];
int head[N];
int len;
inline void add_edge(int u, int v) {e[++len] = edge(head[u], v); head[u] = len;}
int n;
ll ans = 0;
int root;
int dep[N];
int c[N];
std::vector<int> cnt[N];
void dfs(int cur, int FA) {
if (cur == root) {
for (int i = head[cur]; i; i = e[i].next) {
dfs(e[i].to, cur);
}
return;
}
int d = dep[cur] = dep[FA] + 1;
if (d % 2 == 0) c[d / 2]++;
cnt[d].clear();
int sum = 0;
for (int i = head[cur]; i; i = e[i].next) {
if (e[i].to == FA) continue;
c[d] = 0;
dfs(e[i].to, cur);
sum += c[d];
cnt[d].push_back(c[d]);
}
if (cnt[d].size() > 1) {
for (std::vector<int>::iterator i = cnt[d].begin(); i != cnt[d].end(); ++i) {
ans += 1ll * (*i) * (sum - *i);
}
}
}
int main() {
scanf("%d", &n);
int u, v;
for (int i = 1; i <= n - 1; i++) {
scanf("%d%d", &u, &v);
add_edge(u, v); add_edge(v, u);
}
for (int i = 1; i <= n; i++) {
root = i;
dep[root] = 0;
dfs(root, 0);
}
printf("%lld", ans / 6);
return 0;
}
```