P3629

Aryper · 2021-06-27 19:33:08 · 个人记录

[APIO2010]巡逻

似乎只用树的直径就可以完全解决这道题。。

当 K=1 时，只加入一条边。我们发现加入边必然会使树中的一部分边与其组成环，很显然这一部分边是一条链，且加入边之后这条链上的所有边都只用走一次就可以了。

反正我是感性理解的，因为人太菜确实不会证明。

那么显然我们需要找最长链就是树的直径。

当 K=2 时，我又开始了感性的理解。

其实这种情况（如果在 K=1 已经证明）下，我还是可以稍微解释一下的。

我们所得到的的结果只有两种，一种是两个环相互没有交集，一种是有交集。

那么在没有交集的情况下，我们只要找到两条相互没有交集的链，且它们的长度之和最长即可。

另一种有交集的情况下， 其实可以相当于上一种情况，只不过改变了一下连接方式而已。但这种情况下我们有着树的直径的解法。

以有交集的情况讨论，我想出了一种感性理解的做法。

首先求出树的直径，把直径上所有的边权赋值为 -1 ，然后用树形 DP （那个两次DFS/BFS在边权为负时不可用）求出此时树的直径。然后答案什么的就好求了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,k,u,v,ans,tot,ma,q,tmp;

ll ver[N*2+5],wt[N*2+5],nxt[N*2+5],head[N+5],fa[N+5],vis[N+5],dt[N+5];

void dfs(ll p,ll dis) {
    vis[p]=1;dt[p]=dis;
    if(dt[p]>=ma) {
        ma=dt[p];q=p;
    }
    for(ll i=head[p];i;i=nxt[i]) {
        if(!vis[ver[i]]) dfs(ver[i],dis+wt[i]);
        else continue;
        fa[ver[i]]=p;
    }
}

void dp(ll p) {
    vis[p]=1;
    for(ll i=head[p];i;i=nxt[i]) {
        if(vis[ver[i]]) continue;
        dp(ver[i]);
        tmp=max(tmp,dt[p]+dt[ver[i]]+wt[i]);
        dt[p]=max(dt[p],dt[ver[i]]+wt[i]);
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;wt[tot]=1;
    nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();k=read();

    for(ll i=1;i<n;i++) {
        u=read();v=read();add(u,v);add(v,u);
    }

    dfs(1,0);
    memset(vis,0,sizeof(vis));memset(dt,0,sizeof(dt));
    memset(fa,0,sizeof(fa));ma=0;
    dfs(q,0);

    if(k==1) {
        ans=(n-1)*2-dt[q]+1;
        write(ans);
    }
    else {
        for(ll i=q;i!=0;i=fa[i]) {
            for(ll j=head[i];j;j=nxt[j]) {
                if(ver[j]==fa[i]) {
                    wt[j]=-1;break;
                }
            }
            for(ll j=head[fa[i]];j;j=nxt[j]) {
                if(ver[j]==i) {
                    wt[j]=-1;break;
                }
            }
        }
        ans=(n-1)*2-dt[q]+1;
        memset(vis,0,sizeof(vis));
        memset(dt,0,sizeof(dt));
        dp(1);
        ans=ans-tmp+1;
        write(ans);
    }

    return 0;
}