题解 P3565 【[POI2014]HOT-Hotels】

$$\color{cornflowerblue}{\mathcal{Treaker}}$$ # 树形DP 这题比较难想~~对于我这种DP蒟蒻~~ 我们设两个数组$f[x][i]$表示以$x$为根的子树里到$x$距离为$i$的节点个数，$g[x][i]$以$x$为根的子树内，再来一条长度为$i$的链就能形成方案的节点个数。 转移方程如下：还是比较好理解的 这个$n$不要太在意，懒得那么细致了。 ```cpp 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$呢。 两种情况，一种是两个点在左边，一个点在右边；还有一种是两个点在右边，一个点在左边。 $g$数组的话，分3种情况，一种是原来就有的，另一种是一个点在左边，另一个点在右边，还有一种是全在右边。 $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; } ```