bzoj 1912 巡逻(树直径)

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。

首先对于k=1的数据，yy一下就可以发现要找树的直径，然而对于k=2的点，相当于找两条直径，但是会发现，如果这两条直径重复了会很蛋疼，还是会重复走到，因此我们找完第一个直径后，直径上面的边全部赋值为-1，然后再找第二条直径。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 int tot,go[],first[],next[];

 int op[];

 int vis[],dis[],c[],from[],pre[];

 int d[],n,k,ans,Mx2,val[];

 void insert(int x,int y,int z){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     val[tot]=z;

 }

 void add(int x,int y,int z){

     insert(x,y,z);op[tot]=tot+;

     insert(y,x,z);op[tot]=tot-;

 }

 void bfs(int x){

     int h=,t=;

     for (int i=;i<=n;i++) pre[i]=from[i]=;

     for (int i=;i<=n;i++) vis[i]=,dis[i]=;

     c[]=x;vis[x]=;dis[x]=;

     while (h<=t){

         h++;

         for (int i=first[c[h]];i;i=next[i]){

             int pur=go[i];

             if (vis[pur]) continue;

             pre[pur]=c[h];

             from[pur]=i;

             vis[pur]=;c[++t]=pur;dis[pur]=dis[c[h]]+val[i];

         }

     }

 }

 void pianfen1(){

     bfs();

     int mx=;

     for (int i=;i<=n;i++) if (dis[i]>dis[mx]) mx=i;

     bfs(mx);

     Mx2=;

     for (int i=;i<=n;i++) if (dis[Mx2]<dis[i]) Mx2=i;

     if (k==) printf("%d\n",*(n-)-dis[Mx2]+);

 }

 void dfs(int x){

     d[x]=,vis[x]=;int mx1=,mx2=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (vis[pur]) continue;

         dfs(pur);

         if (d[pur]+val[i]>mx1) mx2=mx1,mx1=d[pur]+val[i];

         else

         if (d[pur]+val[i]>mx2) mx2=d[pur]+val[i];

     }

     if (mx1+mx2>ans) ans=mx1+mx2;

     d[x]=mx1;

 }

 int main(){

     scanf("%d%d",&n,&k);

     for (int i=;i<n;i++){

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y,);

     }

     pianfen1();

     int cnt=*(n-)-dis[Mx2]+;

     if (k==) return ;

     for (int i=;i<=n;i++) vis[i]=,d[i]=0x3f3f3f3f;

     for (int i=Mx2;i!=;i=pre[i]) val[from[i]]=-,val[op[from[i]]]=-;

     ans=;

     dfs();

     printf("%d\n",cnt-ans+);

 }

秒客网