bzoj1912(树形dp)

Posted on   |   In

题解

  • $ k=1 $ 必然连接直径两端
  • 我们考虑$ k=2 $的情况 首先明确选的两条路径 选直径是否还是最优的?当然,不管如何考虑选直径带来的优势要大于不选直径 然后对于第二条路的选择 如果第二条路和直径有交边 那么交边还是会经过两次 那么就是让 两条路径并起来的部分减去交的部分长度最长 我们可以考虑将选出来的直径的边权置$-1$ 然后再求一遍树的直径 这样子就必然能得到最优解

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int t){o->t=y;o->v=t;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
 
int n,k;
bool vis[MAXN];
int dis[MAXN];
queue<int>que;
pii bfs(int x){
    inc(i,1,n)vis[i]=dis[i]=0;
    que.push(x);vis[x]=1;
    while(!que.empty()){
    int y=que.front();que.pop();
    link(y){
        if(!vis[j->t])vis[j->t]=1,dis[j->t]=dis[y]+j->v,que.push(j->t);
    }
    }
    pii pos=mp(x,0);
    inc(i,1,n)if(dis[pos.first]<dis[i])pos=mp(i,dis[i]);
    return pos;
}
 
int fa[MAXN];
 
void dfs(int x,int pre){
    fa[x]=pre;
    link(x){
    if(j->t==pre)continue;
    dfs(j->t,x);
    }
}
 
void _dfs(int x,int pre){
    link(x){
    if(j->t==pre){continue;}
    if(vis[j->t])j->v=-1,_dfs(j->t,x);
    }
}
 
int dp[MAXN],dp1[MAXN];
int st[MAXN],tot;
bool cmp(int x,int y){return x>y;}
 
void __dfs(int x,int pre){
    link(x){
    if(j->t==pre)continue;
    __dfs(j->t,x);
    dp[x]=max(dp[x],dp[j->t]);
    }
    tot=0;
    link(x){
    if(j->t==pre)continue;
    st[++tot]=dp1[j->t]+j->v;
    }
    sort(st+1,st+tot+1,cmp);
 //   cout<<x<<"::: "<<tot<<" "<<st[1]<<endl;
    if(tot==0)return ;
    else if(tot==1)dp[x]=max(dp[x],st[1]),dp1[x]=st[1];
    else dp[x]=max(dp[x],max(st[1]+st[2],st[1])),dp1[x]=st[1];
 //   cout<<x<<"::: "<<dp[x]<<endl;
}
 
int main(){
    n=read();k=read();
    int x,y;
    inc(i,2,n)x=read(),y=read(),add(x,y,1),add(y,x,1);
    int ans=2*(n-1);
    pii t1,t2;
    t1=bfs(1);t2=bfs(t1.first);
    ans-=t2.second-1;
    if(k==2){
    inc(i,1,n)vis[i]=0;
    x=t2.first;y=t1.first;
    dfs(y,0);
    while(x){
        vis[x]=1;
        x=fa[x];
    }
    _dfs(y,0);__dfs(y,0);
    ans-=dp[y]-1;
    }
    printf("%d\n",ans);
    return 0;
}

题目描述

https://www.lydsy.com/JudgeOnline/problem.php?id=1912

Input

第一行包含两个整数$n$,$K(1 ≤ K ≤ 2)$.接下来$n – 1$行，每行两个整数 $a, b$,表示村庄$a$与$b$之间有一条道路$(1 ≤ a, b ≤ n)$。

Output

输出一个整数，表示新建了$K$条道路后能达到的最小巡逻距离。