P3629 [APIO2010] 巡逻-526互联

P3629 [APIO2010] 巡逻

/*
树的直径的变形题，用树形dp求解
用直径是因为直径大,然后在求一个直径

对于k=2
对于某一条边，如果两者重合了，那对ans的影响不变
否则权值减去1

所以只需要将第一次的边进行标记，然后求最大的直径就可以了

奇怪的树直径

*/
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int M=2e5+5;

int mx,w[M];
int h[M],ne[M<<1],e[M<<1],tot;
void add(int from,int to) {
    e[++tot]=to; ne[tot]=h[from]; h[from]=tot;
}

int root1,root2;
int f[M],son[M];
void dfs(int now,int fa) {
    vector<pii>v;
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa)continue;
        dfs(to,now);
        if(f[to]+w[to]>f[now])f[now]=f[to]+w[to],son[now]=to;
        v.push_back({f[to]+w[to],to});
    }
    sort(v.rbegin(),v.rend());
    if(v.size()==0)f[now]=0;//这个点是跟节点
    else {
        if(v[0].first>mx)mx=v[0].first,root1=v[0].second;
        if(v.size()>=2&&v[0].first+v[1].first>mx) {
            mx=v[0].first+v[1].first;
            root1=v[0].second,root2=v[1].second;
        }
    }
}

void up() {
    while(root1)w[root1]=-1,root1=son[root1];
    while(root2)w[root2]=-1,root2=son[root2];
}

int main() {
    int n,k;
    cin>>n>>k;
    for(int i=2;i<=n;i++)w[i]=1;
    for(int i=1;i<n;i++) {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    if(k==1) {
        cout<<2*(n-1)-mx+1<<endl;
        return 0;
    }
    up();
    int tmp=mx;mx=0;
    for(int i=1;i<=n;i++)f[i]=-1e9;
    dfs(1,0);
    cout<<2*(n-1)-mx-tmp+2<<endl;
    return 0;
}

P3629

3629