【題解】bzoj1912（同洛谷P3629）[APIO2010]巡邏 樹的直徑

題目連結

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。

最初線路總長度為2 * (n-1)，當K=1時，找到樹的最長鍊，設長度為L1，答案為2 * (n-1)-L1+1；當K=2時，将直徑邊權取反，再次求直徑，設長度為L2，答案為2*n-L1-L2。

#include<cstdio>
const int N=+;
struct Edge{
    int v,w,nx;
}edge[N<<];
int head[N],tot=,n,k,pre1[N],pre2[N],len,rt;
inline void addedge(int u,int v)
{
    edge[++tot].v=v;
    edge[tot].w=;
    edge[tot].nx=head[u];
    head[u]=tot;
}
int dfs(int u,int fa)
{
    int mx1=,mx2=;//最長路與次長路 
    for(int i=head[u];i;i=edge[i].nx)
    {
        int v=edge[i].v;
        if(v!=fa)
        {
            int w=edge[i].w+dfs(v,u);
            if(w>mx1)mx2=mx1,mx1=w,pre2[u]=pre1[u],pre1[u]=i;
            else if(w>mx2)mx2=w,pre2[u]=i;
        }
    }
    if(mx1+mx2>len)len=mx1+mx2,rt=u;
    return mx1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&k);
    int u,v,ans=*(n-);
    for(int i=;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    dfs(,);ans=ans-len+;
    if(k==)
    {
        len=;
        for(int i=pre1[rt];i;i=pre1[edge[i].v])edge[i].w=edge[i^].w=-;//成對變換修改正反邊
        for(int i=pre2[rt];i;i=pre1[edge[i].v])edge[i].w=edge[i^].w=-;
        dfs(,);
        ans=ans-len+; 
    }
    printf("%d\n",ans);
    return ;
}
           

總結

通過邊權取反的方法處理兩個環重疊的情況，非常巧妙。