【bzoj1912】【Apio2010】【巡逻】【树的直径】

Description

Input

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b，表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。

Output

输出一个整数，表示新建了K 条道路后能达到的最小巡逻距离。

Sample Input

8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Sample Output

HINT

10%的数据中，n ≤ 1000, K = 1；
30%的数据中，K = 1；
80%的数据中，每个村庄相邻的村庄数不超过 25；
90%的数据中，每个村庄相邻的村庄数不超过 150；
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

题解：首先。第一条边肯定连在直径两端。。然后把直径上的边都设成-1.在求一遍直径。然后第二条边还是连在直径两端即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
int ans,point[N],cnt(1),n,k,x,y,next[N*2],temp,f1[N],f2[N],m,d1[N],d2[N];
struct use{int en,v;}e[N*2];
void add(int x,int y){next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].v=1;}
void dfs(int x,int fa){
   for (int i=point[x];i;i=next[i])
     if (e[i].en!=fa){
        dfs(e[i].en,x);int t=e[i].v+f1[e[i].en];
        if (t>f1[x])f2[x]=f1[x],f1[x]=t,d2[x]=d1[x],d1[x]=i;
        else if (t>f2[x]) f2[x]=t,d2[x]=i;
     }  
   if (f1[x]+f2[x]>temp) temp=f1[x]+f2[x],m=x;
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}
    ans=2*(n-1);dfs(1,0);ans=ans-temp+1;temp=0;
    if (k==2){
       memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));
       for (int i=d1[m];i;i=d1[e[i].en]) e[i].v=e[i^1].v=-1;    
       for (int i=d2[m];i;i=d1[e[i].en]) e[i].v=e[i^1].v=-1;
       dfs(1,0);ans=ans-temp+1;
    }
   cout<<ans<<endl;
}

秒客网