-
题目链接：
-
分析
最近被众多dalao暴虐，这道题傻逼地调了两天才知道错哪
不过这题比较良心给你一个容易发现性质的图
-
不修路时
每条路走两次可知需要走(2(N-1))步
-
(K=1)
送分给你，直接(O(N))求直径,若直径长为(L),由于新加路还要走一步,少走了(L-1)步
-
(K=2)
如果还是用求直径的方法来求发现不太对,与原来直径重叠那部分又要多走一遍
，于是不妨把原来直径边权取反再求一边直径，若长为L',因为已经减去重叠部分还是少走((L'-1))步,答案就为(2(N-1)-L-L')
-
-
注意
好象直径取反后不能简单地用dfs求直径,因为在第一次找最远点时可能得到一个错误的答案，于是就用DP来求，顺便学了一下DP求直径
-
DP求树的直径
(D[v_i])表示在以(v_i)为根子树内走到的最大深度
转移：(v_1,v_2...v_k)是(v_i)子树内节点 (D[i]=max_{1<=j<=k}(D[v_j]+edge(v_i,v_j)))
若(v_a,v_b)是(v_x)子树内两节点,树的直径可以看作由四部分组成:
(D[v_a]+edge(v_a,v_x)+edge(v_x,v_b)+D[v_b])
具体看代码实现
-
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <map>
#include <queue>
#include <algorithm>
#define ri register int
#define ll long long
using namespace std;
const int maxn=100005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,k;
struct Edge{
int ne,to,dis;
}edge[maxn<<2];
int num_edge=-1,h[maxn];
int s,t;
inline void add_edge(int f,int t){
edge[++num_edge].ne=h[f];
edge[num_edge].to=t;
edge[num_edge].dis=1;
h[f]=num_edge;
}
int mx=-inf,vis[maxn];
void dfs_1(int fa,int cur,int cnt){
for(ri i=h[cur];i!=-1;i=edge[i].ne){
if(edge[i].to!=fa){
dfs_1(cur,edge[i].to,cnt+1);
}
}
if(cnt>mx){
mx=cnt,t=cur;
}
return ;
}
int pre[maxn],dmet[maxn],tot=0,ex=0;
void dfs_2(int fa,int cur,int cnt){
for(ri i=h[cur];i!=-1;i=edge[i].ne){
if(edge[i].to!=fa){
dfs_2(cur,edge[i].to,cnt+1);
pre[edge[i].to]=cur;
}
}
if(cnt>mx){
mx=cnt,s=cur;
}
return ;
}
int diameter;
void dfs_3(int fa,int cur,int cnt){
if(cur==t){
diameter=cnt;
return ;
}
for(ri i=h[cur];i!=-1;i=edge[i].ne){
int v=edge[i].to;
if(vis[v]&&v!=fa){
dfs_3(cur,v,cnt+1);
edge[i].dis=-1;
edge[i^1].dis=-1;
}
}
return ;
}
int d[maxn];
void dp(int fa,int now){
for(ri i=h[now];i!=-1;i=edge[i].ne){
int v=edge[i].to;
if(v==fa)continue;
dp(now,v);
mx=max(mx,d[now]+d[v]+edge[i].dis);//上一次循环已更新一次d[now]
d[now]=max(d[now],d[v]+edge[i].dis);
}
return ;
}
int main(){
int x,y;
read(n),read(k);
memset(h,-1,sizeof(h));
for(ri i=1;i<n;i++){
read(x),read(y);
add_edge(x,y);
add_edge(y,x);
}
memset(vis,0,sizeof(vis));
dfs_1(0,1,0);
mx=-inf;
dfs_2(0,t,0);
int tmp=s;
while(tmp!=t){
vis[tmp]=1;
dmet[++tot]=tmp;
tmp=pre[tmp];
}
dmet[++tot]=t,vis[t]=1;
dfs_3(0,s,0);
//cout<<s<<' '<<t<<' '<<diameter<<endl;
/*-------*/
if(k==2){
mx=0;
dp(0,1);
int diameter_2=mx;
//cout<<mx<<endl;
if(mx<0)diameter_2=0;
printf("%d
",2*n-diameter-diameter_2);
}
else{
printf("%d
",2*(n-1)-(diameter-1));
}
return 0;
}