题解 P5904 【[POI2014]HOT-Hotels 加强版】

既然n到达了10w, 所以bzoj3522中的换根dp显然是不可取的，本题的树根就是1. 首先, 我们考虑一下有几种情况可以使得三个点在树上的距离彼此之间的距离两两相等? 事实上，只有下面这种情况

令f[i][j]表示i子树中距离i的距离是j的节点个数. 令g[i][j]是i子树中，有多少个二元组(x,y)满足 dis(x, lca(x, y)) = dis(y, lca(x, y)) = dis(lca(x, y), i) + j

这样的话, 可以得到如下dp转移方程

ans += f[i][j - 1] * g[to][j];
ans += f[to][j] * g[i][j + 1]; // 更新答案

g[i][j + 1] += f[to][j] * f[i][j + 1];
g[i][j - 1] += g[to][j]; // 更新 g[i]

f[i][j + 1] += f[to][j]; // 更新f[i]

其中to是当前节点i的儿子节点. 第一行成立的原因是 第二行成立的原因是 注意，上面考虑ans的贡献来自的两部分, 不能要求x,y,z三个点都完全来自前面已经考察过的子树或者完全来自当前正在考察to子树, 否则那是递归已经解决的问题了（即已经做过贡献了，如果这里再算的话, 就是重复计数）.

第五行和第七行都很容易理解（直接根据f、g的定义就是）.

第四行成立的原因是 注意我们的dp转移方程，仅仅和深度有关, 所以可以使用长链剖分优化.

至此，此题已破~

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
//#define LOCAL
#define int long long
#define re register int
#define FE(x) for(int h = head[x], to; ~h; h = gg[h].nxt)
const int maxn = 200005;
int n, cnt, head[maxn], height[maxn], son[maxn], dep[maxn], *f[maxn << 2], *g[maxn << 2], ans, tmpf[maxn << 2], tmpg[maxn << 2], *posf, *posg;
struct Arc
{
    int from, to, nxt;
} gg[maxn << 1];

inline void addarc(int from, int to)
{
    gg[cnt].from = from, gg[cnt].to = to, gg[cnt].nxt = head[from];
    head[from] = cnt++;
}

void dfs(int cur, int fa)
{
    height[cur] = dep[cur] = dep[fa] + 1;
    FE(cur)
    {
        to = gg[h].to;
        if (to ^ fa)
        {
            dfs(to, cur);
            if (height[cur] < height[to])
            {
                height[cur] = height[to];
                son[cur] = to;
            }
        }
    }
}

void dfs1(int cur, int fa)
{
    f[cur][0] = 1;
    if (son[cur])
    {
        f[son[cur]] = f[cur] + 1;
        g[son[cur]] = g[cur] - 1;
        dfs1(son[cur], cur);
    }
    ans += g[cur][0]; // 图1中j = 0的特殊情况
    FE(cur)
    {
        to = gg[h].to;
        if (to ^ fa && to ^ son[cur])
        {
            int len = height[to] - dep[to] + 1;
            f[to] = posf;
            posf += len;
            posg += len * 2 + 10;
            g[to] = posg;
            ++posg;
            dfs1(to, cur);
            for (re j = 0; j < len; j++)
            {
                if (j)
                {
                    ans += f[cur][j - 1] * g[to][j];
                }
                ans += f[to][j] * g[cur][j + 1];
                g[cur][j + 1] += f[to][j] * f[cur][j + 1];
            }
            for (re j = 0; j < len; j++)
            {
                if (j)
                {
                    g[cur][j - 1] += g[to][j];
                }
                f[cur][j + 1] += f[to][j];
            }
        }
    }
}

signed main()
{
#ifdef LOCAL
    freopen("d:\\data.in", "r", stdin);
//  freopen("d:\\my.out", "w", stdout);
#endif
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (re i = 1, a, b; i < n; i++)
    {
        scanf("%lld%lld", &a, &b);
        addarc(a, b);
        addarc(b, a);
    }
    dep[1] = 1;
    dfs(1, 0);
    posf = tmpf, posg = tmpg;
    int len = height[1];
    f[1] = posf;
    posf += len;
    posg += len * 2 + 10;
    g[1] = posg;
    ++posg;
    dfs1(1, 0);
    printf("%lld", ans);
    return 0;
}

ac情况 （洛谷和bzoj均过了~）

所属题目
P5904 [POI2014]HOT-Hotels 加强版
评测状态
Accepted
评测分数
100
编程语言
C++
代码长度
2.08KB
用时
325ms
内存
30.63MB

关于上述代码的说明

为什么103行需要开辟两倍空间? 还特喵的要+10? 显然这个10是自己YY的, 也就是要求比2倍的空间还要大
这是因为代码第69行. 因为f是正向的, 所以不需要开辟两倍空间, 但是本题的g是倒向的
（即父节点的g继承长儿子的g是 g[cur] = g[to] - 1）,所以就像下图