M_sea

洛谷3698 [CQOI2017]小Q的棋盘
LuoguBZOJ分析显然从根节点出发走一条链不回头是最优的。于是跑一遍$\texttt{dfs}$找到以根节点为...
扫描右侧二维码阅读全文
30
2019/01

洛谷3698 [CQOI2017]小Q的棋盘

Luogu

BZOJ

分析

显然从根节点出发走一条链不回头是最优的。

于是跑一遍$\texttt{dfs}$找到以根节点为一个端点的最长的链,设长度为$L$,然后分类讨论:

  • 如果$L>m$,因为只能走$m$步,所以答案为$m+1$。
  • 如果$L\leq m$,那么显然可以多走$m-L+1$步,也就是可以多访问$\frac{m-L+1}{2}$个点,所以答案为$\min\left\{n,L+\frac{m-L+1}{2}\right\}$。

正确性好像比较显然...反正我不会证就是了...

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

struct Edge { int v,nxt; };
Edge e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m,L=0;

inline void dfs(int u,int fa,int dep) {
    L=max(L,dep);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u,dep+1);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<n;++i) {
        int u=read()+1,v=read()+1;
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0,1);
    if (L>=m) printf("%d\n",m+1);
    else printf("%d\n",min(n,L+(m-L+1)/2));
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 10 PM

发表评论