P3565 [POI2014]HOT-Hotels

參考題解

題目大意：
給定一棵樹，在樹上選 3 個(gè)點(diǎn)，要求兩兩距離相等，求方案數(shù)。

三個(gè)點(diǎn)樹上兩兩距離為d存在下面兩種情況

• 某個(gè)點(diǎn)三個(gè)子樹（保證該點(diǎn)是LCA）中分別由三個(gè)點(diǎn)距離它為d
• 對(duì)于某一個(gè)點(diǎn)，它的 d 級(jí)祖先以及子樹內(nèi)兩個(gè)以它為L(zhǎng)CA，距它 d 的點(diǎn)

對(duì)于情況一，設(shè)計(jì)dp： $f_{u,j}$表示以$u$為根的子樹，距i距離為$j$的點(diǎn)數(shù)

對(duì)于情況二，設(shè)計(jì)dp：$g_{u,j}$表示以$u$為根的子樹，兩個(gè)點(diǎn)的到LCA距離相等（此出用d表示），LCA到$u$的距離為$d?j$的點(diǎn)對(duì)

對(duì)于$f_{u,j}$的狀態(tài)轉(zhuǎn)移十分顯然：$f_{u,j}={\sum }_{v\in so{n}_u}{f}_{v,j?1}$

而對(duì)于$g_{u,j}$來說存在兩種情況

• 某個(gè)子樹內(nèi)部存在兩個(gè)點(diǎn)：$g_{u,j}={\sum }_{v\in so{n}_u}{g}_{v,j+1}$
• 兩個(gè)不同的子樹各貢獻(xiàn)一個(gè)點(diǎn)，以$u$為L(zhǎng)CA：$g_{u,j}={\sum }_{v,w\in so{n}_u,v=w}{f}_{v,j?1}\times f_{w,j?1}$

很明顯，第二中情況$f_{v,j?1}\times f_{w,j?1},f_{w,j?1}\times f_{v,j?1}$是同一種情況，這里我們讓$v$是$u$較靠前的兒子即可避免重復(fù)計(jì)算

而對(duì)于答案計(jì)算來說也存在兩種情況：
首先對(duì)于三個(gè)點(diǎn)樹上兩兩距離為d的情況都可以看成兩個(gè)點(diǎn)在一個(gè)子樹中，而另一個(gè)點(diǎn)“別處”

• 在子樹$v$中選一個(gè)點(diǎn)，而在其他子樹中選兩個(gè)點(diǎn)：$g_{u,j+1}\times f_{v,j}$
• 在子樹$v$中選兩個(gè)點(diǎn)，而在其他子樹中選一個(gè)點(diǎn)：$f_{u,j?1}\times g_{v,j}$

同樣為了避免重復(fù)計(jì)算只需要讓其他子樹搞成$v$前面的子樹即可
注意上述$g_{u,j+1}$和$f_{u,j?1}$都還未算$v$對(duì)其的貢獻(xiàn)，這個(gè)只需要先計(jì)算答案在加貢獻(xiàn)即可。

計(jì)算狀態(tài)數(shù)組和答案時(shí)，都有計(jì)算前面子樹的情況，直接運(yùn)用前綴和的思想即可邊計(jì)算答案，邊轉(zhuǎn)移數(shù)組。

這里要提一點(diǎn)，我們至今沒有提到$g_{u,0}$對(duì)答案的貢獻(xiàn)，它確實(shí)對(duì)答案有貢獻(xiàn)，但是我們已經(jīng)計(jì)算過了，如果在此加上會(huì)重復(fù)計(jì)算。

而其他博主在計(jì)算的時(shí)候加上$g_{u,0}$實(shí)際上增加的時(shí)$g_{wson,1}$即重兒子的貢獻(xiàn)。

根據(jù)g的轉(zhuǎn)移方程可知道：$g_{u,0}$的貢獻(xiàn)全部來自于${\sum }_{v\in so{n}_u}{g}_{v,1}$，而計(jì)算$f_{u,j?1}\times g_{v,j}$對(duì)答案的貢獻(xiàn)時(shí)我們具體寫一下$f_{u,0}\times g_{v,1}$而$f_{u,0}=1$，因此已經(jīng)計(jì)算過$g_{u,0}$的貢獻(xiàn)！！！

---

然后就是長(zhǎng)鏈剖分優(yōu)化dp，每次保存長(zhǎng)兒子的貢獻(xiàn)，其他兒子暴力合并，每條長(zhǎng)鏈都會(huì)在鏈頭暴力合并一次時(shí)間復(fù)雜度$O(len)$總的合并時(shí)間復(fù)雜度$O(n)$

最后如果寫指針版本的話，由于g數(shù)組是倒著轉(zhuǎn)移的，$f$要多開一倍的內(nèi)存，否則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];// 加上重兒子的貢獻(xiàn)}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);// 邊計(jì)算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];}// 邊轉(zhuǎn)移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;//多開一倍的內(nèi)存g[1]=now;now+=dep[1];dfs2(1,0);cout<<ans<<'\n';return 0; }

菜菜的我搞了一天這個(gè)題啊啊啊啊

總結(jié)

以上是生活随笔為你收集整理的P3565 [POI2014]HOT-Hotels（树形dp+长链剖分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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