BZOJ

分析

长链剖分入门题。

接着原题推。

之前那样子是$O(n^2)$的，考虑继续优化。

注意转移时的式子：

$\large f[i][j]=\sum f[son][j-1]$

$\large g[i][j]=\sum \Big(g[son][j+1]+f[i][j]\times f[son][i-1]\Big)$

如果只有一个儿子，就变成了

$\large f[i][j]=f[son][j-1]$

$\large g[i][j]=g[son][j+1]$

写成指针的形式，变成了

$\large f[i]=f[son]-1,g[i]=g[son]+1$

于是可以上长链剖分，$O(1)$继承重儿子，再$O(\sum len)$合并轻儿子。

总时间复杂度是$O(n)$的。

具体实现见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+100;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n;
int height[MAXN],hson[MAXN];

inline void dfs1(int u,int fa) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs1(v,u); height[u]=max(height[u],height[v]);
        if (!hson[u]||height[v]>height[hson[u]]) hson[u]=v;
    }
    height[u]=height[hson[u]]+1; //这一句话要写到最后，不然会RE
}

ll *f[MAXN],*g[MAXN],tmp[MAXN<<2],*id=tmp;
ll ans=0;

inline void dfs(int u,int fa) {
    if (hson[u]) f[hson[u]]=f[u]+1,g[hson[u]]=g[u]-1,dfs(hson[u],u);
    f[u][0]=1,ans+=g[u][0];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa||v==hson[u]) continue;
        f[v]=id,id+=(height[v]<<1); g[v]=id,id+=(height[v]<<1);
        dfs(v,u);
        for (re int j=0;j<height[v];++j) {
            if (j) ans+=f[u][j-1]*g[v][j];
            ans+=g[u][j+1]*f[v][j];
        }
        for (re int j=0;j<height[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() {
    n=read();
    for (re int i=1,u,v;i<n;++i) {
        u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    dfs1(1,0);
    f[1]=id,id+=(height[1]<<1); g[1]=id,id+=(height[1]<<1);
    dfs(1,0);
    printf("%lld\n",ans);
    return 0;
}