题解 P3565 【[POI2014]HOT-Hotels】
Treaker
·
·
题解
\color{cornflowerblue}{\mathcal{Treaker}}
树形DP
这题比较难想对于我这种DP蒟蒻
我们设两个数组f[x][i]表示以x为根的子树里到x距离为i的节点个数，g[x][i]以x为根的子树内，再来一条长度为i的链就能形成方案的节点个数。
转移方程如下：还是比较好理解的
这个n不要太在意，懒得那么细致了。
for(int i = 0;i <= n;i ++) ans += g[x][i] * (i == 0 ? 0 : f[to][i-1]) + g[to][i+1] * f[x][i];
for(int i = 0;i <= n;i ++) g[x][i] += f[x][i] * (i == 0 ? 0 : f[to][i-1]) + g[to][i+1];
for(int i = 1;i <= n;i ++) f[x][i] += f[to][i-1];
肿么统计ans呢。
两种情况，一种是两个点在左边，一个点在右边；还有一种是两个点在右边，一个点在左边。
$f$更简单了，不多赘述
暴力代码如下：（更精彩的在后面）
```cpp
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int N = 5001;
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 << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n;
int dep[N] , f[N][N] , g[N][N];
ll ans;
struct Edge
{
int to; Edge *nxt;
Edge(int to,Edge *nxt) : to(to) , nxt(nxt) {}
}*head[N];
inline void add(int u,int v) {head[u] = new Edge(v,head[u]);}
void get_tree(int x)
{
f[x][0] = 1;
for(Edge *i = head[x];i;i = i -> nxt)
{
int to = i -> to;
if(dep[to]) continue;
dep[to] = dep[x] + 1;
get_tree(to);
for(int i = 0;i <= n;i ++) ans += g[x][i] * (i == 0 ? 0 : f[to][i-1]) + g[to][i+1] * f[x][i];
for(int i = 0;i <= n;i ++) g[x][i] += f[x][i] * (i == 0 ? 0 : f[to][i-1]) + g[to][i+1];
for(int i = 1;i <= n;i ++) f[x][i] += f[to][i-1];
}
}
int main()
{
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
n = read();
for(int i = 1 , u , v;i < n;i ++)
{
u = read(); v = read();
add(u,v); add(v,u);
}
dep[1] = 1;
get_tree(1);
printf("%lld\n",ans);
return 0;
}
```
我又回来了，如果$n$是$1e5$考虑如何优化。
先给他长链剖分（学过树剖应该都知道），那么对它进行势能分析，然后他就成$O(n)$的了？？？
可没这么简单，这样的复杂度的前提是我们直接处理长儿子（手动滑稽），
我们直接把长儿子赋给$x$，然后在对短儿子进行处理
势能分析的话是：这里$u$是$x$的子节点
$$\sum_{x=1}^n((\sum_uh(u)) - h(x))$$
它会相互抵消，最后就是近似$O(n)$.
这里采用了指针是因为，直接开数组真的开不下。
我们开一个大数组，每个节点都从大数组里面取一段出来赋值，节省空间。
我这里采用从上向下赋地址，因为我从下往上赋一直RE（我对内存的理解还是太浅显了）。
细节代码如下：
```cpp
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int N = 100005 , M = 100005;
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 << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n;
int dep[M] , hs[M] , in[M] , fa[M] , h[M];
ll ans , pool[N << 2] , *f[M] , *g[M] , *tail = pool;
struct Edge
{
int to; Edge *nxt;
Edge(int to,Edge *nxt) : to(to) , nxt(nxt) {}
}*head[N];
inline void add(int u,int v) {head[u] = new Edge(v,head[u]); in[v] ++;}
void get_tree(int x)
{
h[x] = 1;
for(Edge *i = head[x];i;i = i -> nxt)
{
int to = i -> to;
if(dep[to]) continue;
fa[to] = x;
dep[to] = dep[x] + 1;
get_tree(to);
h[x] = max(h[x],h[to] + 1);
if(h[to] > h[hs[x]]) hs[x] = to;
}
}
void dfs(int x)
{
if(hs[x])
{
f[hs[x]] = f[x] + 1;
g[hs[x]] = g[x] - 1;
dfs(hs[x]);
}
f[x][0] = 1; ans += g[x][0];
for(Edge *i = head[x];i;i = i -> nxt)
{
int to = i -> to;
if(to == hs[x] || to == fa[x]) continue;
f[to] = tail; tail += h[to] << 1; g[to] = tail; tail += h[to] << 1;
dfs(to);
for(int j = 0;j <= h[to];j ++) ans += g[x][j] * (j == 0 ? 0 : f[to][j-1]) + g[to][j+1] * f[x][j];
for(int j = 0;j <= h[to];j ++) g[x][j] += f[x][j] * (j == 0 ? 0 : f[to][j-1]) + g[to][j+1];
for(int j = 1;j <= h[to];j ++) f[x][j] += f[to][j-1];
}
}
int main()
{
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
n = read();
for(int i = 1 , u , v;i < n;i ++)
{
u = read(); v = read();
add(u,v); add(v,u);
}
dep[1] = 1;
get_tree(1); f[1] = tail; tail += h[1] << 1; g[1] = tail; tail += h[1] << 1;
dfs(1);
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
```