題意

input

5
1 2
2 3
3 4
4 5

output

1

限制與約定

\(3≤n≤200000\)

題解

如果只放一個(gè)點(diǎn)，很顯然就是放在直徑的中點(diǎn)上面，這樣一定是最優(yōu)的，
\[Ans=(len(直徑)+1)/2\]而現(xiàn)在題目要求取兩個(gè)點(diǎn)，
我們想象在兩點(diǎn)路徑的中點(diǎn)及其子樹到兩點(diǎn)的路徑均相等，
而在中點(diǎn)右邊（沒有中點(diǎn)一樣）到右邊選的點(diǎn)的距離一定小于到左邊選的點(diǎn)的距離。
當(dāng)然，左邊同理。
即現(xiàn)在題目要求斷開一條邊，然后使得兩個(gè)部分的最長直徑最短。
而斷開這條邊的位置，一定是在原來那棵樹的直徑上面。
于是呢，就把直徑抽出來，把直徑上每個(gè)點(diǎn)及其子樹（子樹不包括直徑上其他點(diǎn)）
都記錄一個(gè)最長直徑，以及以這個(gè)點(diǎn)開始能走的最長距離與次長距離。
求出斷開每一條邊的左半部分的直徑分別是多少，
在處理一遍右邊的，組合一下就好了

code

#include <bits/stdc++.h>
#define re register int
#define inf 1e9
using namespace std;
inline void read(int &x){x=0;char ch=getchar();for(;!isdigit(ch);ch=getchar());for(; isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48); 
}
inline void print(int x){if(x>9)print(x/10);putchar((x%10)+48);}
const int N=200010;
int n,q,f[N],to[N<<1],nx[N<<1],h[N],d[N],c,v[N],l[N][4],g[N],dis[N],ans=N;
inline void add(int u,int v){to[++c]=v,nx[c]=h[u],h[u]=c;}
inline void dfs(int x,int fa){f[x]=fa,d[x]=d[fa]+1;for(re i=h[x];i;i=nx[i])if(to[i]!=fa)dfs(to[i],x);
}
inline void get(int x,int fa){l[x][1]=l[x][2]=l[x][3]=0;for(re i=h[x];i;i=nx[i])if(to[i]!=fa&&!v[to[i]]){get(to[i],x);re tmp=l[to[i]][1]+1;if(tmp>=l[x][1])l[x][2]=l[x][1],l[x][1]=tmp;else if(tmp>l[x][2])l[x][2]=tmp;l[x][3]=max(l[to[i]][3],(l[x][1]+l[x][2]));}
}
signed main(){freopen("ob.in","r",stdin);freopen("ob.out","w",stdout); read(n);int x,y,l1=0,l2=0;for(re i=1;i<n;++i) read(x),read(y),add(x,y),add(y,x); dfs(1,0);for(re i=1;i<=n;++i) if(d[i]>d[l1]) l1=i;dfs(l1,0);for(re i=1;i<=n;++i) if(d[i]>d[l2]) l2=i;for(re i=l2;i;i=f[i]) v[i]=1;for(re i=l2;i;i=f[i]) get(i,0);for(re i=l2;i;i=f[i]){g[f[i]]=i;re tmp=l[g[i]][1]+1;if(g[i]==0) tmp=0;if(tmp>=l[i][1])l[i][2]=l[i][1],l[i][1]=tmp;else if(tmp>l[i][2])l[i][2]=tmp;dis[i]=l[i][3]=max(l[g[i]][3],(l[i][1]+l[i][2]));}for(re i=l2;i;i=f[i]) get(i,0);for(re i=l1;i;i=g[i]){re tmp=l[f[i]][1]+1;if(f[i]==0) tmp=0;if(tmp>=l[i][1])l[i][2]=l[i][1],l[i][1]=tmp;else if(tmp>l[i][2])l[i][2]=tmp;l[i][3]=max(l[f[i]][3],(l[i][1]+l[i][2]));ans=min(ans,max(l[i][3],dis[g[i]]));}print((ans+1)>>1);return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Sparks-Pion/p/9691346.html

總結(jié)

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

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