bzoj1912 [Apio2010]patrol 巡邏（樹的直徑[變式]）

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

11

HINT

10%的資料中，n ≤ 1000, K = 1；

30%的資料中，K = 1；

80%的資料中，每個村莊相鄰的村莊數不超過 25；

90%的資料中，每個村莊相鄰的村莊數不超過 150；

100%的資料中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

分析：

先考慮K==1的情況

加了一條邊之後，圖就變成了一棵環套樹

顯然我們如果要讓巡邏距離盡可能短，那麼就要使環上的邊盡量多，

（因為不在環上的邊都要走兩遍）

怎麼讓環大呢，

就是讓添加邊變成環之前的那條鍊盡可能長

這就是樹上最長鍊

樹的直徑

求法：

兩遍dfs，

第一遍dfs找到一個最遠點，再從最遠點dfs，最後得出的最長dis就是樹的直徑

那麼K==1的時候就是求一個直徑dis

ans=2*(n-1-dis)+dis+1

K==2時，就是在K==1求出解得基礎上，求一個次長直徑

注意

如果我們什麼處理都沒有，直接求一個次長鍊（次短路方法），

可能會和最長鍊重合，那麼最長鍊上的一部分就會走兩遍

是以我們在求出最長鍊之後，把最長鍊上的邊權賦為-1，

這樣再跑一個裸的直徑就好了

（這樣就可以保證可以在新求出的直徑中盡量少重合原先的直徑）

tip

代碼中我用了兩種求直徑的方法

注意dp傳回值是目前點的f值

然而答案要單獨統計

這裡寫代碼片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=;
struct node{
    int x,y,nxt,v;
};
node way[N<<];
int st[N],tot=-,n,K;
int len1,len2,pre[N],ansx,ans;
int f[N],g[N];

void add(int u,int w,int z)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
    tot++;
    way[tot].x=w;way[tot].y=u;way[tot].v=z;way[tot].nxt=st[w];st[w]=tot;
}

void dfs(int now,int fa,int dis)
{
    if (dis>ans)
    {
        ans=dis;
        ansx=now;
    }
    for (int i=st[now];i!=-;i=way[i].nxt)
        if (way[i].y!=fa)
        {
            pre[way[i].y]=i;
            dfs(way[i].y,now,dis+way[i].v);
        }
}

void change(int s,int t)
{
    for (int i=t;i!=s;i=way[pre[i]].x)
    {
        way[pre[i]].v=-;
        way[pre[i]^].v=-;
    }
}

int dp(int now,int fa)
{
    f[now]=;g[now]=;
    for (int i=st[now];i!=-;i=way[i].nxt)
        if (way[i].y!=fa)
        {
            int len=dp(way[i].y,now)+way[i].v;
            if (len>f[now])
            {
                g[now]=f[now];
                f[now]=len;
            }
            else if (len>g[now]) g[now]=len;
        }
    len2=max(len2,f[now]+g[now]);   //統計答案 
    return f[now];  //dp傳回的是最長鍊 
}

int main()
{
    memset(st,-,sizeof(st));
    scanf("%d%d",&n,&K);
    for (int i=;i<n;i++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add(u,w,);
    }

    memset(pre,-,sizeof(pre));
    ans=ansx=;
    dfs(,,);
    int p=ansx;
    ans=ansx=;
    memset(pre,-,sizeof(pre));
    dfs(p,,);
    if (K==)
    {
        printf("%d",*(n--ans)+ans+);
        return ;
    }

    len1=ans;
    change(p,ansx);
    dp(,);
    printf("%d\n",*(n--len1-len2)+len1+len2+);
    return ;
}