题解 P3565 【[POI2014]HOT-Hotels】

· · 题解

P3565 [POI2014]HOT-Hotels

参考题解

题目大意： 给定一棵树，在树上选 3 个点，要求两两距离相等，求方案数。

三个点树上两两距离为d存在下面两种情况

对于情况一，设计dp： f_{u,j}表示以u为根的子树，距i距离为j的点数

对于情况二，设计dp：g_{u,j}表示以u为根的子树，两个点的到LCA距离相等（此出用d表示），LCA到u的距离为d-j的点对

对于f_{u,j}的状态转移十分显然：f_{u,j}=\sum_{v\in son_u }f_{v,j-1}

而对于g_{u,j}来说存在两种情况

很明显，第二中情况f_{v,j-1}×f_{w,j-1}, f_{w,j-1}×f_{v,j-1}是同一种情况，这里我们让v是u较靠前的儿子即可避免重复计算

而对于答案计算来说也存在两种情况： 首先对于三个点树上两两距离为d的情况都可以看成两个点在一个子树中，而另一个点“别处”

同样为了避免重复计算只需要让其他子树搞成v前面的子树即可 注意上述g_{u,j+1}和f_{u,j-1}都还未算v对其的贡献，这个只需要先计算答案在加贡献即可。

计算状态数组和答案时，都有计算前面子树的情况，直接运用前缀和的思想即可边计算答案，边转移数组。

这里要提一点，我们至今没有提到g_{u,0}对答案的贡献，它确实对答案有贡献，但是我们已经计算过了，如果在此加上会重复计算。

而其他博主在计算的时候加上g_{u,0}实际上增加的时g_{wson,1}即重儿子的贡献。

根据g的转移方程可知道：g_{u,0}的贡献全部来自于\sum_{v\in son_u}g_{v,1}，而计算f_{u,j-1}×g_{v,j}对答案的贡献时我们具体写一下f_{u,0}×g_{v,1}而f_{u,0}=1，因此已经计算过g_{u,0}的贡献！！！

然后就是长链剖分优化dp，每次保存长儿子的贡献，其他儿子暴力合并，每条长链都会在链头暴力合并一次时间复杂度O(len)总的合并时间复杂度O(n)

最后如果写指针版本的话，由于g数组是倒着转移的，f要多开一倍的内存，否则g可能倒回来覆盖掉f

code

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr int N=5010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int n;
int dep[N],son[N];
void dfs1(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        dfs1(v,u);
        if(dep[v]>dep[son[u]]) son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}

ll pool[4*N];
ll *f[N],*g[N],*now=pool;
ll ans;
void dfs2(int u,int fa)
{
    f[u][0]=1;
    if(son[u])
    {
        f[son[u]]=f[u]+1;
        g[son[u]]=g[u]-1;
        dfs2(son[u],u);
        ans+=g[son[u]][1];// 加上重儿子的贡献
    }
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||v==son[u]) continue;
        f[v]=now;now+=dep[v]<<1;
        g[v]=now;now+=dep[v];
        dfs2(v,u);
        // 边计算
        for(int j=0;j<dep[v];j++)
        {
            if(j) ans+=f[u][j-1]*g[v][j];
            ans+=g[u][j+1]*f[v][j];
        }
        // 边转移
        for(int j=0;j<dep[v];j++)
        {
            g[u][j+1]+=f[u][j+1]*f[v][j];
            if(j) g[u][j-1]+=g[v][j];
            f[u][j+1]+=f[v][j];
        }
    }

}
int main()
{
    IO;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    f[1]=now;now+=dep[1]<<1;//多开一倍的内存
    g[1]=now;now+=dep[1];
    dfs2(1,0);
    cout<<ans<<'\n';
    return 0;
}

菜菜的我搞了一天这个题啊啊啊啊