題目：CF120F Spiders

DP - 樹形DP - 樹的直徑 - 圖論 - 樹 - bfs

題目大意

給出 $n$ 棵樹，你每次可以選擇兩個樹，并將這兩棵樹的兩個節(jié)點粘起來，形成一棵新的樹。經(jīng)過 $n?1$ 次操作后，這 $n$ 棵樹就融合為了一棵樹
問最后這棵樹的最大直徑（最長鏈）長度

解題思路

以前看到有些題是要求直徑最短，看到這題之后松了口氣

因為最后要求的是最長鏈，所以，每一棵樹都要把自己的最長鏈（直徑）貢獻給最終答案
那么我們就把 $n$ 棵樹的直徑粘成一段不就好了嗎

換句話說：設(shè)第 $i$ 棵樹的直徑端點為 $u_i,v_i$，$[x,y]$ 表示一個將點 $x$ 和點 $y$ 粘起來的操作。
那么就：$[v_1,u_2],[v_2,u_3]\dots [v_{n?1},u_n]$
最后的答案就是 $n$ 棵樹的直徑之和了

#include<cstdio> #include<iostream> #include<vector> using namespace std; const int Maxn=1010,inf=0x3f3f3f3f; int dis[Maxn],f[Maxn]; int n,ans; vector <int> e[Maxn]; inline int read() {int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s*w; } void dfs(int x,int fa) {int m1=0,m2=0;for(int i=0;i<e[x].size();++i){int y=e[x][i];if(y==fa)continue;dfs(y,x);f[x]=max(f[x],f[y]+1);int tmp=f[y]+1;if(tmp>m1)m2=m1,m1=tmp;else if(tmp>m2)m2=tmp;}dis[x]=max(m1+m2,max(m1,m2)); } int main() {freopen("input.txt","r",stdin); // 注意這題提交的時候要帶文件輸入輸出freopen("output.txt","w",stdout);int T=read();while(T--){n=read();int tot=0;for(int i=1;i<n;++i){int x=read(),y=read();e[x].push_back(y);e[y].push_back(x);}dfs(1,0);for(int i=1;i<=n;++i)tot=max(tot,dis[i]);ans+=tot;for(int i=1;i<=n;++i){e[i].clear();dis[i]=f[i]=0;}}printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF120F Spiders 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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