正題

---

題目大意

$n$個點的無根樹，求兩條不相交的路徑使它們長度之積最大。

---

解題思路

我們暴力枚舉第一條，然后求樹的直徑即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=210; struct node{int to,next; }a[N*2]; int n,dis,ans,tot,f[N],ls[N]; bool v[N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dp(int x,int fa){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa) continue;dp(y,x);if(!v[x]) dis=max(dis,f[x]+f[y]+1);f[x]=max(f[y]+1,f[x]);}if(v[x]) f[x]=-1; } void dfs(int x,int fa,int z){v[x]=1;dis=0;memset(f,0,sizeof(f));dp(1,1);ans=max(ans,dis*z);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa) continue;dfs(y,x,z+1);}v[x]=0; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}for(int i=1;i<=n;i++)dfs(i,i,0);printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的nssl1438-战略威慑【枚举,树的直径】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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