题目描述
APIO2010 巡逻 (考察对于树的直径的理解)
算法1
(暴力枚举) $O(n)$
其实如果只加一条边的话肯定是加直径的两个端点,这个很显然,那么就是如果加的是两条边的话就需要仔细思考一下,我们不难发现如果需要加两条边的话那么加的第二条边就是去除第一条个直径之外的第二大的直径,那么怎么就这个第二大的直径就成为了关键,如果按照dfs的方法来求的话就会出现问题,因为第一条直径有很多条,所以我们无法确实能够是那一条直径,所以第二个直径需要dp来求取。答案就是2 *(n - 1) - 直径1 - 直径2
C++ 代码
#include <bits/stdc++.h>
#define N 1000010
using namespace std;
struct node {
int f,t,val,nex;
}rt[N];
int head[N];
int cnt;
void add(int x,int y) {
rt[cnt].f = x;
rt[cnt].t = y;
rt[cnt].val = 1;
rt[cnt].nex = head[x];
head[x] = cnt ++;
}
int a,b;
int l1,l2;
int vis[N];
int dep[N];
int maxx;
int num;
int dp1[N];
int dp2[N];
void dfs(int x) {
for(int i = head[x];i != -1;i = rt[i].nex) {
if(!vis[rt[i].t]) {
dep[rt[i].t] = dep[x] + 1;
vis[rt[i].t] = 1;
if(dep[rt[i].t] > maxx)
maxx = dep[rt[i].t],num = rt[i].t;
dfs(rt[i].t);
}
}
}
void dfs1(int x) {
if(dep[x] == 1)
return ;
for(int i = head[x];i != -1;i = rt[i].nex) {
if(dep[rt[i].t] == dep[x] - 1) {
rt[i].val = -1;
rt[i ^ 1].val = -1;
dfs1(rt[i].t);
}
}
}
void dfs2(int x,int f) {
for(int i = head[x];i != -1;i = rt[i].nex) {
if(rt[i].t != f) {
dfs2(rt[i].t,x);
if(dp1[x] < dp1[rt[i].t] + rt[i].val) {
dp2[x] = dp1[x];
dp1[x] = dp1[rt[i].t] + rt[i].val;
}
else if(dp2[x] < dp1[rt[i].t] + rt[i].val ) {
dp2[x] = dp1[rt[i].t] + rt[i].val;
}
}
l2 = max(l2,dp1[x] + dp2[x]);
}
}
int main() {
memset(head,-1,sizeof head);
cin>>a>>b;
int x,y;
for(int i = 1;i <= a - 1;i ++) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
vis[1] = 1;
dep[1] = 1;
dfs(1);
memset(vis,0,sizeof vis);
memset(dep,0,sizeof dep);
dep[num] = 1;
vis[num] = 1;
maxx = 0;
dfs(num);
l1 = dep[num];
if(b == 1) {
cout<<2 * (a - 1) - l1 + 2;
//cout<<l1;
return 0;
}
if(l1 == a - 1)
cout<<a + 1;
else {
dfs1(num);
dfs2(1,0);
cout<<2 * a - l1 - l2 + 1;
return 0;
}
}
/*
8 2
1 2
3 1
3 4
5 3
7 5
8 5
5 6
* */