此博客停更

好久没写题解了，于是就来口胡一发

基于这道t，由于百度找不到题解→。→于是我就来写了~

题目大意：给你一棵树，选出K条路径，使得覆盖的点数最大

解：

首先它是一棵树，选出的路径同样也要是一棵树（可以证明

然后选出的树一定包含直径= =（显然

于是在直径上出发贪心找2*K-1条链，每次找到最长的一条删掉这样似乎是O(nlgn)，算是一种暴力（能过）吧

于是来讲下我的做法：

Ans=∑min(Si,2*K);

Si表示：将树分层，像套娃一样，叶子节点为第一层，剥掉第一层叶子后，第二层为去掉叶子后成为叶子的点，以此类推，Si表示每层的点数（原谅我语文长期不及格

证明：

最优性：画图可知，一条路径每层最多经过2*K个结点，于是Ans为上界

可行性：将叶子节点所在那层称为外层，其余为内层，于是注意内层点，当内层点覆盖完全后，余下的叶结点可任意匹配来构成路径，于是可知路径条数不超过K

/********************************************************** 
    Problem: 1517 
    User: qiancl 
    Language: C++ 
    Result: Accepted 
    Time:2060 ms 
    Memory:29224 kb 
***********************************************************/
  
#include<cstring> 
#include<cstdio> 
#include<algorithm> 
using namespace std;
#define nc() getchar()
inline int read(){ 
    int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); 
    for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; 
} 
#define min(a,b) (a<b?a:b) 
int du[1000005],cnt,last[1000005],n,mx,ans,L,q[1000005];bool o[1000005]; 
struct edge{int to,next;}e[2000005]; 
inline void add(int u,int v){ 
    e[++cnt]=(edge){v,last[u]},last[u]=cnt,++du[v]; 
    e[++cnt]=(edge){u,last[v]},last[v]=cnt,++du[u]; 
} 
int main(){ 
    n=read(),(L=read())*=2;for(int i=1;i<n;add(read(),read()),++i); 
    int l=1,r=0;for(int i=1;i<=n;++i)if(du[i]==1)q[++r]=i,o[i]=1; 
    while(l<=r){ 
        int k=r-l+1;ans+=min(L,k); 
        for(int j=1;j<=k;++j){ 
            int now=q[l++]; 
            for(int i=last[now];i;i=e[i].next)if(!o[e[i].to]){ 
                if(--du[e[i].to]==1)q[++r]=e[i].to,o[e[i].to]=1;; 
            } 
        } 
    } 
    printf("%d",ans); 
}

loading...