題意：給一棵 $n$ 個點的樹，求兩兩距離相等的三元組個數(shù)。

$n\le 10^5$

顯然相當(dāng)于是找一個點到這三個點距離相等。子樹內(nèi)和子樹外到當(dāng)前點的距離為某個值的點的個數(shù)可以長鏈剖分快速得到，但統(tǒng)計答案非常棘手。

接下來是個鬼才想得到的 dp：

$f(u,x)$ 為 $u$ 子樹內(nèi)距離 $u$ 距離為 $x$ 的點的個數(shù)，這個比較好求。

$g(u,x)$ 表示假想 $u$ 子樹外有一個距離為 $x$ 的點，在子樹內(nèi)選兩個點與這個假想點形成合法三元組的方案數(shù)。

鳥語翻譯：在 $u$ 子樹內(nèi)找兩個深度相同的點，若它們到它們的 lca （不一定是 $u$）距離為 $d$ ，那么這個 lca 到 $u$ 的距離必須是 $u?x$，求符合條件的兩個點的對數(shù)。

也就是我們把這個 $g$ 當(dāng)接口，乘一個子樹外為 $x$ 的點的個數(shù)，就可以直接得到某個范圍內(nèi)的合法三元組個數(shù)。

考慮加入一個子樹 $v$，$f$ 的轉(zhuǎn)移很顯然

$$f(u,x)?f(u,x)+f(v,x?1)$$

考慮 $g$ 的轉(zhuǎn)移

• 兩個都在 $u$ 這邊: $g(u,x)?g(u,x)$
• 兩個都在 $v$ 這邊: $g(u,x)?g(v,x+1)$
• 一個 $u$ 一個 $v$,此時的 lca 一定是 $u$:$g(u,x)?f(u,x)f(v,x?1)$

綜上

$$g(u,x)?g(u,x)+g(v,x+1)+f(u,x)f(v,x?1)$$

然后在 dp 的時候順便算答案

$$ans?ans+f(u,x)g(v,x+1)+f(v,x)g(u,x+1)$$

長鏈剖分優(yōu)化， $f$ 往后繼承，$g$ 往前繼承，輕兒子暴力轉(zhuǎn)移。繼承的時候 $u$ 是空的，只有 $f(u,0)g(so{n}_u,1)$ 會影響答案，之后對答案的貢獻就可以暴力算了。

注意 $g$ 要開兩倍在中間取指針，前面用來繼承后面用來存信息。

復(fù)雜度 $\mathrm{O}(n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #define MAXN 100005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } typedef long long ll; vector<int> e[MAXN]; ll buf[MAXN<<3],*cur=buf; inline ll* newbuf(int x){ll* p=cur;cur+=x;return p;} int fa[MAXN],mx[MAXN],son[MAXN]; void dfs(int u,int f) {fa[u]=f;for (int i=0;i<(int)e[u].size();i++)if (e[u][i]!=f){dfs(e[u][i],u);if (mx[e[u][i]]>mx[son[u]]) son[u]=e[u][i];}mx[u]=mx[son[u]]+1; } ll *f[MAXN],*g[MAXN]; ll ans; void dfs(int u) {*f[u]=1;if (son[u]) f[son[u]]=f[u]+1,g[son[u]]=g[u]-1,dfs(son[u]),ans+=*g[u];;for (int i=0;i<(int)e[u].size();i++)if (e[u][i]!=fa[u]&&e[u][i]!=son[u]){int v=e[u][i];f[v]=newbuf(mx[v]),g[v]=newbuf(2*mx[v])+mx[v]-1;dfs(v);for (int j=1;j<=mx[v];j++)ans+=f[u][j-1]*g[v][j];for (int j=0;j<=mx[v]&&j<mx[u];j++)ans+=g[u][j+1]*f[v][j];for (int j=1;j<=mx[v];j++) g[u][j-1]+=g[v][j],g[u][j]+=f[u][j]*f[v][j-1];for (int j=0;j<=mx[v]&&j<mx[u];j++)f[u][j+1]+=f[v][j];} // printf("f[%d]:",u); // for (int i=0;i<=mx[u];i++) printf("%lld ",f[u][i]); // puts(""); // printf("g[%d]:",u); // for (int i=0;i<=mx[u];i++) printf("%lld ",g[u][i]); // puts(""); } int main() { // freopen("test.in","r",stdin);int n=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();e[u].push_back(v),e[v].push_back(u); } dfs(1,0),f[1]=newbuf(mx[1]),g[1]=newbuf(2*mx[1])+mx[1]-1,dfs(1);cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【BZOJ4543】Hotel加强版【神仙树形dp】【长链剖分】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。